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.
This screams merge sort (for time efficiency) to me which I don't think has a nice in-place algorithm (O(1) space). You could see [this question](https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm) for an in-place merge sort. 

I agree with Ani, if you *really* need O(1) space it will probably be easier to just use something like [quicksort](http://en.wikipedia.org/wiki/Quicksort).