CODEWITHSUNDEEP
algorithmsorting
user1071840
user1071840

Reputation: 3592

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

[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.

Upvotes: 6

Views: 4517

Answers (5)

Debashis
Debashis

Reputation: 81

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;
}

Upvotes: 1

Jimmy
Jimmy

Reputation: 11

    // 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;
            }
   }

Upvotes: 1

btilly
btilly

Reputation: 46399

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.

Upvotes: 6

user1952500
user1952500

Reputation: 6771

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.

Upvotes: 0

Jim Mischel
Jim Mischel

Reputation: 133975

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.

Upvotes: 4

Related Questions