In-place sort an array with 2 sorted sub-arrays

Question

[This is an interview question. I couldn't find a duplicate.]

An array contains two sub- sorted arrays. Give an inplace algorithm to sort two sub arrays.

for ex: I/P: 1 4 5 7 8 9 2 3 6 10 11 O/P: 1 2 3 4 5 6 7 8 9 10 11

I thought in terms of in-place merge sort, insertion sort (since the sub-arrays are already sorted) and in terms of quick-sort but couldn't think of a solution which gives me better complexity than using standard sorting methods.

Please help me find an algorithm which allows us to leverage the sorted sub-array property and result in better time complexity than running Quicksort on the input.

This is the merge sort simulation I thought of, using this example:

  1) For position 0, Comparing 1 & 2, 1 is smaller let it stay at it's original place
  2) For position 1, Comparing 2 & 4, 2 is smaller so swap 2 and 4
  3) For position 2, Comparison now is between 4 and 3 (5 > 4 anyways) swap 3 and 5
  4) For position 3, Comparison between 4 & 5, swap 4 and 7
  5) For position 4, Comparison between 7 & 5, swap 8 and 5 
  6) For position 5, Comparison between 7 & 8 (OUCH!!) it should have been between 7 & 6

It seems that this problem is similar to sorting sorted rows of a matrix, where in-place merge is too complicated.

possible duplicate of [how to merge two sorted integer array in place using O(n) time and O(1) space cost](http://stackoverflow.com/questions/2126219/how-to-merge-two-sorted-integer-array-in-place-using-on-time-and-o1-space-co) — Rafał Dowgird, Mar 14 '13 at 08:17

score 6 · Accepted Answer · answered Mar 14 '13 at 16:42

See http://comjnl.oxfordjournals.org/content/38/8/681.full.pdf+html for a linear time algorithm for solving this exact problem, and an indication of how much effort was spent coming up with that solution.

My guess is that the interviewer had some cute answer that they thought worked, which doesn't really. The second best guess is that they didn't specify the complexity for a reason.

In an interview I would actually have said, "I don't know how to do this efficiently, though I am sure that there is research on that question. But here is an inefficient answer." Then I'd do something that will clearly work.

score 4 · Answer 2 · edited May 23 '17 at 12:14

4

There is an in-place merge sort that has O(n log n) worst-case behavior, but as the paper says, "due to the constant factors involved the algorithm is predominantly of theoretical interest." See https://stackoverflow.com/a/2571104/56778

If you can't allocate a temporary buffer that's as big as one of the sorted subarrays, in-place merging is exceedingly difficult.

edited May 23 '17 at 12:14

Community

1
1

answered Mar 14 '13 at 03:48

Jim Mischel

131,090
20
188
351

score 1 · Answer 3 · answered Jul 25 '13 at 12:29

    // since both are sorted use array b as min heap
    // if a[i] > b[0] (top of min-heap), exch it and heapify b
    // order : O(nlog(n))
   void inplaceMerge(vector<int>& a, vector<int>& b)
   {
     for (int i=0; i < a.size(); i++)  {
         if (a[i] > b[0]) {
                swap(a[i], b[0]);
                sink(b, 0, b.size()-1); // bubbleDown() operation in heap() 
         }
      }
      sort(b.begin(), b.end());   
    }

   void sink(vector<int>& b, int i, int n)
   {
            int j = 2*i + 1;
            while (j <= n) {
                 if (j+1 < n && b[j+1] < b[j]) j++;
                 if (b[j] < b[i]) swap(b[i], b[j]);
                 else break;
                 i = j;
                 j = 2*i + 1;
            }
   }

Welcome to Stack Exchange, Jimmy! Some text explaining your approach a little more would be helpful in the future. Thank you for contributing! — Jesse Smith, Jul 25 '13 at 12:49

score 1 · Answer 4 · answered Jul 16 '23 at 10:36

There is this gap method that works in this scenario. The code will look like this.

Time Complexity: O(n log n)

Space Complexity: O(1)

int[] merge(int[] a) {
  int tot=a.length;
  int gap=tot/2 + tot%2;
  while(gap > 0) {
   int p1=0, p2=gap;
   while(p2 < tot) {
     if(a[p1] > a[p2])
       swap(a, p1, p2);

     p1++;
     p2++;
   }
   p2 = nextgap(gap);
  }

  return a;
}

void swap(int[] a,int i,int j) {
   int temp=a[i];
   a[i]=a[j];
   a[j]=temp;
}

int nextgap(int gap) {
 if(gap<=1)
  return 0;
 return gap/2 + gap%2;
}

user1952500 · Answer 5 · 2013-03-14T05:55:29.757

For the interview question, in your algorithm, once you swap the resultant arrays are not separately sorted anymore. You should 'bubble' down the larger swapped element until it gets to the right position and then continue.

Let us take 2 arrays for simplicity with topA and topB as the current positions (initially both are 0). Let the required resultant arrays be A[1..m]..B[1..n]. Here's a pseudocode:

if (A[topA] < B[topB]) {
    swap (A[topA], B[topB])
    index = topB;
    while (B[index] < B[index + 1]) {
        swap(B[index], B[index + 1])
    }
    topB++
} else {
  topA++;
}

At the end of each run of the above the resultant arrays are sorted and smaller. This can be continued until one of the arrays runs out. However the complexity will be larger than O(m+n) due to the bubbling phase.

In-place sort an array with 2 sorted sub-arrays

5 Answers5