Given a k-sorted array, give an algorithm which runs faster than Θ(nlogn) 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?

If you sort the left half of the array and sort the right half of the array, then you only need to do a merge of the two sorted lists of $k$ elements around the middle to potentially put them in the right order. This takes $O(k)$ extra time. So your recursion for running time using this strategy is $T(n) = 2T(n/2) + O(k)$ where the base case is $T(k) = O(k \log k)$. This should solve to $T(n) = O(n \log k)$.
