## Wednesday, March 05, 2008

### [TECH] Sorting partially sorted sequences.

Partially Sorted Sequence: A sequence k1,k2,...kn of n keys such that any key kj differs from its sorted position by atmost d as an example for d=3 we have 3,5,6,1,2,4 I came across this problem recently, turns out that we can solve this problem in several ways in O(nlog(d)) time. I found an interesting and simple way to solve this problem, a simple observation reveals that the smallest element in the entire sequence of n keys exists in the first d keys.


/*Build a heap(min) H with first d elements
*in O(d) time
*/
for(i=d;i<n;i++){
DeleteMin(H); /*output this key*/
InsertHeap(H,ki);
}
/*Note the Heap will have atmost d keys in it
at any time so the Insert and Delete can be done in
O(log(d)) worst case.
*/



(n-d)log(d) = O(nlog(d))