Space complexity question

Question

Possible Duplicate:
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 1

Take a look at this list, 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.

Answer 2

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

Answer 3

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.

Answer 4

I could (of course) be wrong, but I'd guess anything that takes only O(1) space will also have O(N²) 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;
    }
}