sort in o(1) extra memory

Given an array of size n wherein elements keep on increasing monotically upto a certain location
after which they keep on decreasing monotically, then again keep on increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra memory).


  1. Heyy I googled this and found the solution something like this...

    suppose the array is 12345 4321 2345 4321
    it increases then dcreases then increases and decreases again

    first of all in a single scan find the location of decreasing sub-arrays
    here it is 5 to 8 and 13-16
    and reverse the decreasing array.
    so the array becomes
    12345 1234 2345 1234
    now do simple inplace merging of sorted arrays.

    My question is how in place merge can be done in O(n) times...

    I googled K-tonic sort also. Bt dint find any suitable ans/description

    If u hv ne link plz post

  2. i am sorry the merging will take O(k*m),where m is number of elements in first and second list.


Post a Comment

Popular posts from this blog