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.
I could (of course) be wrong, but I'd guess anything that takes only O(1) space will also have O(N2) complexity. Nonetheless, I think you *can* do a (little) bit better than just applying a normal insertion sort.

```
template <class T, class inIter>
void insert(T t, inIter point, inIter end) {
    inIter right = point;
    ++right;
    while (right != end && *right < t) 
        *point++ = *right++;
    *point = t;
}

void ipmerge(std::vector<int> &A) {
    size_t right = A.size()/2;
    for (size_t left = 0; left < A.size()/2;++left) {
        if (A[right] < A[left]) {
            int t = A[left];
            A[left] = A[right];
            insert(t, A.begin()+right, A.end());
        }
        if (left+1 == right)
            ++right;
    }
}

```