Sort a nearly sorted (or K sorted) array | GeeksforGeeks

Sort a nearly sorted (or K sorted) array 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. 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;

Read full article from Sort a nearly sorted (or K sorted) array | GeeksforGeeks