Question

what is an 'almost sorted' or 'K-sorted' array?

Answer 1

Consider an array of n elements, where every element is all things considered k away from its objective position, devise a calculation that sorts in O(n log k) time.

In other words, consider a k-sorted array that is nearly arranged such that every one of the N elements might be lost by close to k position from the correct sorted arranged.

For instance, let us consider k is 2; an element at index 5 in the sorted array can be indexed as 3, 4, 5, 6, 7 in the given array.

Example:

Given array: array[] = {6, 5, 3, 2, 8, 10, 9}

k=3
In the given example, index 0 value ie, 6; can be at at index 0, 1, 2 or 3.

similarly index 2 value ie, 3; can be at index 0,1,2,3, 4,or 5.

similarly index 3 value ie, 2; can be at index 0,1,2,3,4,5,6.

then the output as sorted would be array[] = {2, 3, 5, 6, 8, 9, 10}