title: Performantly argsort two pre-sorted numpy arrays
body: <p>I've got several groups of arrays. Within each group, all arrays are one-dimensional, all with the same length. Within each group is one primary array, which is already sorted.</p>
  
  <p>For example:</p>
  
  <pre><code>grp_1 = [
      np.array([10, 20, 30, 40]),
      np.array(["A", "C", "E", "G"]),
      ]
  
  grp_2 = [
      np.array([15, 25, 35]),
      np.array(["Z", "Y", "X"]),
      ]
  </code></pre>
  
  <p>Now I want to merge corresponding elements in my groups. I want this to happen in such a way so as to make the primary array of the result to be sorted (in a stable manner). For example:</p>
  
  <pre><code>def combine_groups(groups):
      combined_arrays = [np.concatenate([grp[idx] for grp in groups]) for idx in range(len(groups[0]))]
      sort_indices = np.argsort(combined_arrays[0], kind="mergesort")
      # Merge sort rather than quicksort because the former is stable
      return [arr[sort_indices] for arr in combined_arrays]
  </code></pre>
  
  <p>This works and is fine and dandy, but (for arrays much larger than this example) it's much slower than it needs to be. Merge sort is O(N log(N)), whereas merging arrays <em>that are already sorted</em> should be a O(N) affair.</p>
  
  <p>I came across the <code>cytoolz</code> packages, which has a <code>merge_sorted</code> package which blows numpy out of the water when it comes to <em>sorting</em> my primary arrays. Unfortunately, I need to get the resulting indices, so that I can transform the non-primary arrays as well.</p>
  
  <p>So: is the above possible in a faster way than using numpy's <code>argsort</code>?</p>