Sort array with with first half and second half sorted

Question

Possible Duplicate:
Regarding in-place merge in an array

Stumbled upon this interview question. Given an array of size n where first n/2 is sorted and the second half is sorted. Sort the entire array in place. Now what I can think of in place is somewhat like insertion sort, that'll have space complexity as O(1), but time complexity will be more than O(n). Is an O(n) in place solution possible for this problem?

Answer 1

Have two (logical) pointers - lets call them x and y. x points to the 1st element of the first n/2 elements. y points to the 1st element of the second n/2 elements.

If element at y is lesser than the one at x (let's call n(y) and n(x)), then insert n(y) at x and increment x & y by 1. Else increment x by 1 and check again. Once y hits 'n', stop y and keep repeating till x == y.

E.g.

2 4 7 8 1 3 5 6
x       y

1 2 4 7 8 3 5 6
  x       y 

1 2 4 7 8 3 5 6
    x     y

1 2 3 4 7 8 5 6
      x     y

1 2 3 4 7 8 5 6
        x   y  

1 2 3 4 5 7 8 6
          x   y

1 2 3 4 5 6 7 8
            x y

1 2 3 4 5 6 7 8
              (x,y) 

Answer 2

Normally for sorting two already sorted lists, you would use merge sort; the simplest way would be to copy one of the half arrays somewhere. That is not in-place, but works.

Swapping elements doesn't work, as it does not guarantee the maximum value of the first half of the array is less than the minimum value in the right half:

{ 3 4 4 1 2 4 }

swap i=0,j=3

{ 1 4 4 3 2 4 }

swap i=1, j=5

{ 1 2 4 3 4 4 }

Fixing this by further swapping results in an O(N^2) bubble sort.