Given an unsorted array where each element is at most k distance from its position in a sorted array. Which sorting algorithm can be easily modified for this and what is its time complexity?
🎥 Video solution / Text Solution of this question is given below:
Solution: A k-sorted array can be efficiently sorted using a min-heap of size k, yielding O(n log k) time. Answer: (B) Heap Sort with O(n log k)