Sort K-Sorted Array

Given a k-sorted array that is almost sorted such that each of the N elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.


For example,

Input:

arr = [1, 4, 5, 2, 3, 7, 8, 6, 10, 9]
k = 2

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 


A simple solution would be to use a efficient sorting algorithm to sort the whole array again. The worst case time complexity of this approach will be O(nlogn) where n is the size of the input array. This method also do not use the fact that array is k-sorted. We can also use insertion sort that will correct the order in just O(nk) time. Insertion sort performs really well for small values of k but it is not recommended for large value of k (use it for k < 12). We can solve this problem in O(nlogk) using a min heap. The idea is to construct a min-heap of size k+1 and insert first k+1 elements into the heap. Then we remove min from the heap and insert next element from the array into the heap and and continue the process till both array and heap is exhausted. Each pop operation from the heap should insert the correponding top element in its correct position in the array.

 
C++ implementation –
 

Download   Run Code

Output:

1 2 3 4 5 6 7 8 9 10

 

Time complexity of above solution is O(nlogk) as each insertion operation takes O(logk) time.
Auxiliary space used by the program is O(1).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂