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

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

use K-tonic sort.:)

ReplyDeleteHeyy I googled this and found the solution something like this...

ReplyDeletesuppose 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

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

ReplyDelete