CareerCup

The algorithm to do this would be to use an in place string reverse which is order N.
Example: {1,2,3,4,16,12,10,9,8,16,45,90,60,50}

Keep track of how many monotonically decreasing sequences are seen in the array (k) and their starting indexes.
Reverse all monotonically decreasing strings in 1 pass
{1,2,3,4,16, 8,9,10,12, 45, 90, 50, 60}

for all k,
Now find the index where a[i] is less than a[i-1]. move elements up the array by swapping.

The worst case would be kN, and if k << N then it's order N.

Is this a viable solution?

Take example -> 1,2,3,4,5,4,3,6,7.
Scan through the array to find the point where elements decrease. (Position -5 in above example where array starts from 0th position). Therefore, pos1=5
Scan from that position till elements increase again (pos2=7)
Reverse_array(pos1,pos2) -> Reverses content of array between pos1 and pos2.
Repeat the following steps till end of array is reached. Therefore, you have 'k' sorted arrays which needs to be sorted into 1 big array.

This can be done using k-way merge operation ( O(n) time with extra space)
OR
Perform k-way merge ( O(nlogn) time with O(1) space)
[Sorry, can't paste the link to the paper that can do the latter solution]

can't every array be described as above? i dont think i understand the question?

I guess consider an array like this:
{1, 11, 21, 31, 22, 12, 2, 3, 13, 23, 33, 24, 14, 4}

Make sure you get all subarrays sorted in increasing order and then the algorithm is similar to merge algorithm in mergesort.

@Kalyan, then it would take O(nlogn) for the whole to be sorted. This is because we can only spend O(1) space. So for each pair of sorted sub array, we take O(n) but there are logn tournament rounds which rendering O(nlogn) in total. I don't want to discourage you but it turns out that we haven't found a solutions so far. :(

Correction: there are logM tournament rounds where M is the number of sorted sub array. Well, if M is much less than n, O(n logM) should lies super close to O(n). @Kalyan, your approach are the best solution thus far. Such this sorting algorithm may called TimSort.

can we use memmove?

@kalyan, even then its O(N^2) or (N^no of diff patterns)

i don't think this is a correct question.

because a random array can be described by this, only each sub array has a size of 1.

Impossible to do in 0(n) without using extra memory.

It has to be assumed that the number of increasing and decreasing parts is constant, or else sorting would be magically faster than O(n lg n), simply by partitioning the array, sorting each subarray and then applying this "result"

The problem still sounds interesting even if the number of increasing/decreasing parts is constant. It suffices to figure out how to merge two sorted arrays in place, using O(1) extra storage. This is possible by building up the first part of the merged result from min to max in the larger array (call it Array1), and using Array2 to contain two sorted lists of elements waiting to be merged. One of the lists in Array2 is elements displaced from Array1, and the other list is the remaining elements from Array2. The trick is to keep these 2 lists sorted while updating them in O(1) time each time a merge step is performed. One way is to let one list be broken into 2 pieces that flank the other list, and use a few pointers to keep track of the pieces. The pieces can be updated in O(1) time regardless of what happens in a merge step

After the larger left half of the sorted result is stored in Array1 in O(n) time, the algorithm can recurse on Array2, which has size n/2 or smaller, and consists of 2 sorted subarrays.

Question is incorrect
As some one pointed out - any array can be converted to this format
So sorting will take n*n with O(1) space
or n*log n with O(1) space.