title: Most efficient way to sort a 2d array with sorted rows into 1d sorted array
body: <p>Given a 2d array (a matrix) with n rows and k columns, with it's rows sorted, columns unspecified, what would be the most efficient algorithm to sort it?</p>
  
  <p>For exmaple:</p>
  
  <pre><code>Input (n = 3 ; k = 4):
  1 5 8 10
  3 4 5 6
  2 3 3 9
  
  Output:
  1 2 3 3 3 4 5 5 6 8 9 10
  </code></pre>
  
  <p>This is purely algorithmic question, so no specific .sort() methods of some languages help me, as I'm actually intereseted in the runtime complexity.</p>
  
  <p>What I had in mind would be an algorithm as follows:</p>
  
  <pre><code>- Build a Binary Search tree with n nodes. Each node contains:
    ID - of the row it refers to;
    Value - The number at the "head" of the row.
  - Sort the tree where the sorting key are the values.
  - Find the lowest valued node.
  - Do while the tree has a root:
    - Take the lowest value and append it to the new array.
    - Update the node's value to the next one in the same row.
    - If the updated value is null, delete that node.
      - else re-sort the tree.
    - If the node moved, the first node it swapped with will be the next lowest
      - else, if it didn't move, it's the new lowest.
  </code></pre>
  
  <p>If I'm not mistaken the runtime complexity is <code>O(n*k * log n)</code>, Since I'm sorting the tree <code>n*k</code> times, which takes <code>O(log n)</code> time, and process of finding the next lowest is <code>O(1)</code>.</p>
  
  <p>If my complexity calculation is wrong, please let me know.</p>
  
  <p>Is there any way more efficient than this?</p>