Suppose you are given an k-sorted array, in which no element is farther than k positions away from its final (sorted) position. Give an algorithm which will sort such an array. Prove its correctness. Analyze its running time.
I realize the running time must be Θ(nlogk) but have yet to come up with an algorithm that matches this. I've thought about mergesort but the dividing step leads to O(logn). Any ideas on this?
Best Answer
Hint:
One approach might be to take any priority queue with logarithmic bounds (with regard to the size of the queue), and go over the array, inserting elements of the array into the queue, and popping the minimums from the queue into the array.
If done correctly, then this approach would indeed sort the array (the point is to pop the minimum only when you are sure the appropriate element is already in the queue) and the size of the queue would be $O(k)$ (to ensure $O(n \log k)$ time).
I hope this helps $\ddot\smile$