Solving Complexity Issues: Merging Algorithms

[rover13]

Homework Statement

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.

Relevant Equations

?

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 algorithm would be stable and not in place.

 

[pbuk]

Homework Statement:: (a) ... Justify. (b) ... Prove your answers.

Your answers are just guesses, not the justifications and proofs that are asked for. You need to write things down like "let merge sort have asymptotic run time $M(n) = k n \log n$" and work from there.

If 2 sorting algorithms have the same complexity, won’t merging them be pointless in terms of running time?

Not if you can improve $k n \log n$ to, say, $\frac12 k n \log n$ which would be (asymptotically) twice as fast.

 

[valenumr]

Analyze the complexity of heap sorting k/n elements into buckets and then things get icky. How does merge sort perform with those conditions? Does it have better asymptotic behavior?

 

[sysprog]

Analyze the complexity of heap sorting k/n elements into buckets and then things get icky. How does merge sort perform with those conditions? Does it have better asymptotic behavior?

What exactly do you mean by "things get icky"? Some aspects of the problem, e.g. how best to determine the optimal input size on which to partition, introduce some intricacies, but isn't that part of why the problem is included in a CS course of study?

 

[valenumr]

What exactly do you mean by "things get icky"? Some aspects of the problem, e.g. how best to determine the optimal input size on which to partition, introduce some intricacies, but isn't that part of why the problem is included in a CS course of study?

Gosh, this was a while ago thinking on the problem. I'll try and recollect, but I think basically, it's pretty easy to analyze the first step (heap sorting n approximately equal sized arrays). It gets messy thinking how that is helpful for merge sort. I think you can sort each array by heap top node, pop and reheap each array, sort the arrays again, and then wash, rinse, and repeat. It's an interesting problem, but I really never managed to work though it on paper. It was messy. Since merge sort is not in place, it seems feasible, but I never got I final answer for the bucket ratio that would give improvement.

 

[sysprog]

@valenumr, I'm pretty sure that I'm not out of line in supposing that in this context such terms as "icky" and "messy" are more than a little bit lacking in precision.

 

[valenumr]

@valenumr, I'm pretty sure that I'm not out of line in supposing that in this context such terms as "icky" and "messy" are more that a little bit lacking in precision.

Fair point. I tried applying Master's theorem to my approach to the problem, but I guess when I use such terms I mean there was much more writing than I had expected...

 

[valenumr]

@valenumr, I'm pretty sure that I'm not out of line in supposing that in this context such terms as "icky" and "messy" are more that a little bit lacking in precision.

And to be fair, call it the opposite of "elegant". I never got to such an approach.