CareerCup

sounds like a variant of quick sort

can you give an example?

I doubt that constant space is reasonable to achieve for an interview question. Because this question is essentially the merging step of in-place merge sort, which is known to be too difficult to be practical.

Can you explain the question further ? May be an example ?

It is like merging two sorted lists n/2 each

Merge sort in constant space...

I cannot imagine people thinking merge sort can be done in constant space!

We need to use modified Insertion sort.
i.e insert the element of second half within the elements of first half.
The range of search can be limited to improve efficiency.
Sorry, difficult to document the logic.

can be done in constant space but time complexity will be greater than O(n).

comjnl.oxfordjournals.org/cgi/reprint/35/6/643.pdf

I think it can be done in constant space and linear time by taking two pointers at beginning of each sorted position and then swapping and adjusting pointers as we compare the values pointed by them

Total number of integeres : n
As each half contains n/2 sorted integers, Is it safe to assume that we have two sorted array. Modified version of merge sort can be used.

Assume you have two arrays
each one of n/2,
if you start comparing the
element from the last element of each array . if the element in the first half is greater then swap it with the element with the second half element and decrement the counter for first half else decrement the counter for second half.

class InplaceMerger
{
public:
	static void MergeInplace(std::vector<int>& arr)
	{
		auto current1 = arr.begin();
		auto current2 = arr.begin() + arr.size()/2;
		auto end = arr.end();

		while(current1 != end &&  current2 != end)
		{
			if(*current1 > *current2)
			{
				std::swap(*current1, *current2);
			}
			if(current1 + 1 == current2) current2++;
			else current1++;
		}
	}
};