# Sort a nearly sorted (or K sorted) array

Hello Everyone,

Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.
Examples:

Input : arr[] = {6, 5, 3, 2, 8, 10, 9}
k = 3
Output : arr[] = {2, 3, 5, 6, 8, 9, 10}

Input : arr[] = {10, 9, 8, 7, 4, 70, 60, 50}
k = 4
Output : arr[] = {4, 7, 8, 9, 10, 50, 60, 70}

We can use Insertion Sort to sort the elements efficiently. Following is the C code for standard Insertion Sort.

`/* Function to sort an array using insertion sort*/`

`void` `insertionSort(` `int` `A[], ` `int` `size)`

`{`

` ` `int` `i, key, j;`

` ` `for` `(i = 1; i < size; i++)`

` ` `{`

` ` `key = A[i];`

` ` `j = i-1;`

` ` `/* Move elements of A[0..i-1], that are`

` ` `greater than key, to one`

` ` `position ahead of their current position.`

` ` `This loop will run at most k times */`

` ` `while` `(j >= 0 && A[j] > key)`

` ` `{`

` ` `A[j+1] = A[j];`

` ` `j = j-1;`

` ` `}`

` ` `A[j+1] = key;`

` ` `}`

`}`

The inner loop will run at most k times. To move every element to its correct place, at most k elements need to be moved. So overall complexity will be O(nk)
We can sort such arrays more efficiently with the help of Heap data structure . Following is the detailed process that uses Heap.

1. Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time
2. One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.
Removing an element and adding a new element to min heap will take log k time. So overall complexity will be O(k) + O((n-k) * log(k)).

`// A STL based C++ program to sort a nearly sorted array.`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Given an array of size n, where every element`

`// is k away from its target position, sorts the`

`// array in O(n logk) time.`

`int` `sortK(` `int` `arr[], ` `int` `n, ` `int` `k)`

`{`

` ` `// Insert first k+1 items in a priority queue (or min`

` ` `// heap)`

` ` `//(A O(k) operation). We assume, k < n.`

` ` `priority_queue<` `int` `, vector<` `int` `>, greater<` `int` `> > pq(arr, arr + k + 1);`

` ` `// i is index for remaining elements in arr[] and index`

` ` `// is target index of for current minimum element in`

` ` `// Min Heap 'pq'.`

` ` `int` `index = 0;`

` ` `for` `(` `int` `i = k + 1; i < n; i++) {`

` ` `arr[index++] = pq.top();`

` ` `pq.pop();`

` ` `pq.push(arr[i]);`

` ` `}`

` ` `while` `(pq.empty() == ` `false` `) {`

` ` `arr[index++] = pq.top();`

` ` `pq.pop();`

` ` `}`

`}`

`// A utility function to print array elements`

`void` `printArray(` `int` `arr[], ` `int` `size)`

`{`

` ` `for` `(` `int` `i = 0; i < size; i++)`

` ` `cout << arr[i] << ` `" "` `;`

` ` `cout << endl;`

`}`

`// Driver program to test above functions`

`int` `main()`

`{`

` ` `int` `k = 3;`

` ` `int` `arr[] = { 2, 6, 3, 12, 56, 8 };`

` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr);`

` ` `sortK(arr, n, k);`

` ` `cout << ` `"Following is sorted array"` `<< endl;`

` ` `printArray(arr, n);`

` ` `return` `0;`

`}`

Output:

Following is sorted array 2 3 6 8 12 56

The Min Heap based method takes O(n log k) time and uses O(k) auxiliary space.