Question: > 
> **Possible Duplicate:**  
> 
> [Regarding in-place merge in an array](https://stackoverflow.com/questions/3285756/regarding-in-place-merge-in-an-array) 
> 
> 
> 

I have an array, where the first and second half of the array is sorted, e.g.

```
A[] = "2 4 7 1 5 20"

```

No how do I sort the whole array in O(1) space complexity?

Regards,
Mithun

Answer: 
Take a look at [this list](http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms), and take your pick from any of the algorithms that have '`1`' in the 'Memory' column. The fact that the array has some sort of order already is irrelevant if your only requirement is constant auxiliary space, with no other efficiency requirements.
Using pseudo code, here is an in-place two stack merge.

```
i <- 0
mid <- A.size/2
while i < mid:
  if A[i] > A[i+mid] then
    swap A[i] and A[i+mid]
  i <- i + 1

```

It works (is supposed to work) by maintaining the follow invariant: A[1..mid] and A[mid..n] are sorted, and A[1..i] contains elements strictly less than those contained in A[mid..n]. I might have botched the details, but that is the basic idea.