[Solved] CECS328-EC4

Extra Credit 4.

Sort a given random array of n numbers where each element is at most k index away from its position in the sorted array. (Hint: You could make min/max heaps using the first k+1 numbers and then 1- delete the root once 2- add the next element to the heap 3-Repeat 1 and 2 until you cover all the elements. The time complexity of your solution should be O(nlogk).)

Example 1: Input: a = [2, 8, 0, 17, 5, 12] , k = 2,

(Hint: a number at index 4 in our sorted array, can be located in 2, 3, 4, 5, 6 indices in the given array.) Output: [0 2 5 8 12 17]