CODEWITHSUNDEEP
algorithmsortingdata-structuresmergesort
Rover
Rover

Reputation: 1

Merging both merge sort and heap sort together

Suppose you want to improve Merge Sort by first applying Heap Sort to a number of consecutive subarrays. Given an array A, your algorithm subdivides A into subarrays A1, A2 · · · Ak, where k is some power of 2, and applies Heap Sort on each subarray Ai alone. The algorithm proceeds into merging pairs of consecutive subarrays until the array is sorted. For example, if k = 4, you first apply Heap Sort to sort each Ai and then you merge A1 with A2 and A3 with A4, then you apply the merge function once to get the sorted array. (a) Does the proposed algorithm improve the asymptotic running time of Merge Sort when k = 2? How about the case k = log n (or a power of 2 that is closest to log n)? Justify. (b) Is the proposed algorithm stable? Is it in-place? Prove your answers.

So I have this problem to solve, I was thinking that for k=2, the threshold value is too low and inefficient, but I'm not sure when k is at logn or more. If 2 sorting algorithms have the same complexity, won’t merging them be pointless in terms of running time? For b), i think the merged algorithim would be stable and not in place.

what do you think?

Upvotes: 0

Views: 456

Answers (1)

Roman Svistunov
Roman Svistunov

Reputation: 1079

(a) No, for any k this algorithm would not improve the running time of merge sort as it is a comparison-based sorting algorithm and it can be proven that any such algorithm is Ω(n ln n), and merge sort already is O(n ln n).

(b) This algorithm can be in-place because heap sort is an in-place algorithm (using standard binary max heap implementation with array) and there exists an in-place stable merging algorithm. This algorithm can also be made stable using any stable merging and stable heap sort (can be achieved by using pairs (value, initial position) in the heap and lexicographic comparison). Making this algorithm both stable and in-place requires a stable in-place heap and as far as I know, such heap has not yet been invented.

Upvotes: 1

Related Questions