Where is Bottom Up merge sort useful?

Question

I've been reading "Algorithms, 4th Ed" by Sedgewick & Wayne. The book presents two ways of using merge sort. Using standard top down recursive merge sort OR a bottom up merge sort.

Is there any situation in which the bottom up merge sort is preferred over the top-down version?

http://stackoverflow.com/questions/10153393/mergesort-is-bottom-up-faster-than-top-down — Mitch Wheat, Jul 02 '13 at 05:23
@MitchWheat The question discusses the analysis of the two sorting routines. Not the applications. — Nikunj Banka, Jul 02 '13 at 05:25
You choose the application BASED on the complexity analysis! lol! — Mitch Wheat, Jul 02 '13 at 05:25
Both have the same complexity(O(nlogn)). That's why this question was asked. Is there any specific situation where bottom up is better suited or not? — Nikunj Banka, Jul 02 '13 at 05:26

score 9 · Accepted Answer · edited May 23 '17 at 11:44

9

Recursive mergesort requires O(log n) space for the recursion stack, but the bottom-up version lets you do better (no recursion stack, just a few integers keeping track of your position in the input).

If you come across some language that doesn't support recursion and provides you with only limited memory for a stack (perhaps an embedded system?), the bottom-up version will be your only choice.

Here's a bottom-up version that shows what I mean.

edited May 23 '17 at 11:44

Community

1
1

answered Jul 27 '13 at 22:11

user541686

205,094
128
528
886

Not quite... In the usual "uniform cost" model where we assume that we can store an integer containing the size n of the problem in O(1) memory, bottom-up mergesort takes just O(1) space. It's possible (and actually more precise, though also more cumbersome) to instead use a "logarithmic cost" model where space is measured in actual bits instead of sufficiently-large integers, in which case bottom-up mergesort needs O(log n) space (as does *any* algorithm that reads its complete input using array accesses!), but in this model recursive mergesort needs O(log^2 n) space. – j_random_hacker Jul 28 '13 at 21:06
@j_random_hacker: Sorry, you're completely right... for some reason I thought keeping track of the input position needs O(log log N) bits, my bad; thanks for pointing it out. – user541686 Jul 28 '13 at 21:44

Will Ness · Answer 2 · 2014-03-31T12:52:00.367

Bottom up merge sort can work in almost no memory, with the data being sorted kept on external devices (e.g. tapes). I think it's how it used to work in the 50s and 60s, with those big tall tape machines we see in the old movies.

In other words bottom-up merge is an on line algorithm. It can work with no random access at all.

We first process the input tape and write out sorted chunks of 2 elements each as we read the input tape, writing to two tapes, alternating between the two. Then we read by chunks of 2 from the two tapes we've just written to, and write out merged chunks of 4, while alternating between the output tapes. Then we switch the input and the output again and proceed by chunks of 8, etc. In the last run only one tape gets written to - that's the result.

This can be emulated on modern RAM hardware with only O(1) additional memory, with the merging done in-place. To handle the "short dangling tails" problem (for lengths like 2^n+k, for small k), the sweep along the input sequence can be made in a forward or backward direction alternatingly.

score 1 · Answer 3 · edited May 23 '17 at 11:52

1

Having the same complexity there are only small differences, like the order in which it does the merge.. Left-Right-Up for the recursive one and horizontal for the bottom-up. Also being recursive makes it a bit slower sometimes and i think less intuitive.

edited May 23 '17 at 11:52

Community

1
1

answered Jul 02 '13 at 07:59

user2485149

91
7

Where is Bottom Up merge sort useful?

3 Answers3