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 corresponding top element in its correct position in the array.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <bits/stdc++.h> using namespace std; // Function to sort a K-Sorted Array void sortKSortedArray(vector<int> &A, int k) { // create an empty min heap using std::priority_queue // use std::greater as the comparison function for min-heap priority_queue<int, std::vector<int>, std::greater<int>> pq; int n = A.size(); // insert first k elements in the heap for (int i = 0; i <= k; i++) pq.push(A[i]); int index = 0; // do for remaining elements of the array for (int i = k + 1; i < n; i++) { // pop top element from min-heap and assign it to // next available array index A[index++] = pq.top(); pq.pop(); // push next array element into min-heap pq.push(A[i]); } // pop all remaining elements from the min heap and assign it to // next available array index while (!pq.empty()) { A[index++] = pq.top(); pq.pop(); } } // main function int main() { vector<int> A = { 1, 4, 5, 2, 3, 7, 8, 6, 10, 9}; int k = 2; sortKSortedArray(A, k); // print the sorted array for (int i : A) cout << i << " "; return 0; } |

**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(k).

**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 🙂

## Leave a Reply

This sorting function is of type “int” but doesn’t return any value.

Peter, thanks. We will update the code.