Mergesort - Is Bottom-Up faster than Top-Down?

Question

I've been reading "Algorithms, 4th Ed" by Sedgewick & Wayne, and along the way I've been implementing the algorithms discussed in JavaScript.

I recently took the mergesort examples provided in the book to compare top-down and bottom-up approaches... but I'm finding that bottom-up is running faster (I think). See my analysis on my blog. - http://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/

I have not been able to find any discussion that says one method of mergesort should be faster than the other. Is my implementation (or analysis) flawed?

Note: my analysis measures the iterative loops of the algorithm, not strictly the array compares/moves. Perhaps this is flawed or irrelevant?

EDIT: My analysis didn't actually time the speed, so my statement about it running "faster" is a bit misleading. I am tracking the "iterations" through the recursive method (top-down) and the for loops (bottom-up) - and bottom-up appears to use fewer iterations.

Shocker

The compares and interchanges are the key cost items in sort analysis, I'm pretty sure. – Baguette

@Baguette yes, they would normally be the items to analyze when comparing different sorting algorithms. But in this case, they ought to be the same... they're the same algorithm, so that's not what I'm after. My implementation mirrors what is in the book... is it just possible that bottom-up uses fewer loops over/through the array but has the same number of compares/moves? – Shocker

@NiklasB. I see your point... but those aren't contributing to the disparity in my iteration count. If you look at my code, I'm only tracking the iterations inside the recursive/iterative loops. Math.floor() has nothing to do with it - I'm not using a time-based analysis – Shocker

Perhaps "running faster" in my original post is not correct. I'm finding bottom-up loops over the array fewer times, but that may not have anything to do with "speed" – Shocker

Are there any differences when you sort an array whose size is exactly a power of 2? – Baguette

Yes... using array of size 1024, top-down has 22,527 "iterations" while bottom-up has 21,513 "iterations". – Shocker

Answer 1

If by faster you mean fewer "iterations" then yes. If you're wondering about execution time maybe.

The reason is some of those 21,513 iterations are doing more than the 22,527 iterations.

From looking at the source it seems like some of the leaf nodes in your diagram are being sorted together not individually resulting in fewer merges and sorts but them taking longer.

Susquehanna

Good explanation, thank you! I probably need to digest the implementation a bit more, but at least I know I am not totally crazy. I just didn't expect a difference, considering both of my algorithms use the same merge() code. – Shocker

Answer 2

I have not been able to find any discussion that says one method of mergesort should be faster than the other.

Bottom-up and top-down merge sorts, as well as other variants, have been well studied during the 90s. In a nutshell, if you measure the cost as the number of comparisons of individual keys, the best costs are the same (~ (n lg n)/2), the worst cost of top-down is lower than or equal to the worst case of bottom-up (but both ~ n lg n) and the average cost of top-down is lower than or equal to the average case of bottom-up (but both ~ n lg n), where "lg n" is the binary logarithm. The differences stem from the linear terms. Of course, if n=2^p, the two variants are in fact exactly the same. This means that, comparison-wise, top-down is always better than bottom-up. Furthermore, it has been proved that the "half-half" splitting strategy of top-down merge sort is optimal. The research papers are from Flajolet, Golin, Panny, Prodinger, Chen, Hwang and Sedgewick.

Here is what I came up in my book Design and Analysis of Purely Functional Programs (College Publications, UK), in Erlang:

tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T)           -> T.

cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S,    T,      U) -> mrg(tms(S),tms(T)).

mrg(     [],    T)            -> T;
mrg(      S,   [])            -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg(  [X|S],    T)            -> [X|mrg(S,T)].

Note that this is not a stable sort. Also, in Erlang (and OCaml), you need to use aliases (ALIAS=...) in the patterns if you want to save memory. The trick here is to find the middle of the list without knowing its length. This is done by cutr/3 which handles two pointers to the input list: one is incremented by one and the other by two, so when the second reaches the end, the first one is in the middle. (I learnt this from a paper by Olivier Danvy.) This way, you don't need to keep track of the length and you don't duplicate the cells of the second half of the list, so you only need (1/2)n lg n extra space, versus n lg n. This is not well known.

It is often claimed that the bottom-up variant is preferable for functional languages or linked list (Knuth, Panny, Prodinger), but I don't think this is true.

I was puzzled like you by the lack of discussion on merge sorts, so I did my own research and wrote a large chapter about it. I am currently preparing a new edition with more material on merge sorts.

By the way, there are other variants: queue merge sort and on-line merge sort (I discuss the latter in my book).

[EDIT: As the measure for the cost is the number of comparisons, there is no difference between choosing an array versus a linked list. Of course, if you implement the top-down variant with linked lists, you have to be clever, as you don't necessarily know the number of keys, but you'll need to traverse a least half the keys, each time, and reallocate, in total (1/2)n lg n cells (if you are clever). Bottom-up merge sort with linked lists actually requires more extra memory, n lg n + n cells. So, even with linked lists, the top-down variant is the best choice. As far as the length of the program goes, your mileage may vary, but in a functional language, top-down merge sort can be made shorter than bottom-up, if stability is not required. There are some papers that discuss implementations issues of merge sort, like in-place (for which you need arrays), or stability etc. For instance, A Meticulous Analysis of Mergesort Programs, by Katajainen and Larsson Traff (1997).]

Olette

you write "and the average cost of top-down is lower than or equal to the worst case of bottom-up (but both ~ n lg n)" is it so, or did you mean "average case of bottom-up"? Was the analysis done for arrays or is it valid for linked lists too? – Pangolin

thanks; I'd be very much interested in seeing your optimal top-down linked lists functional mergesort, to compare it with this: mgsort xs = foldt merge [] [[x]|x<-xs]. – Pangolin

(I didn't mean to imply it's a one-liner; with all the functions brought together and somewhat inlined, it becomes this 9-liner in Haskell). – Pangolin

I edited the answer. The Haskell version you refer to seems to be a bottom-up variant. It is difficult to compare with other languages because it uses features specific to Haskell. That is why I chose a simplified version of Erlang for my book, so the programs are easily adapted and compared. I also give a translation of the above code into Java, keeping the functional style:-) (There is a chapter about functional style in Java and a forthcoming on XSLT.) – Olette

For an array or vector, top down merge sort involves n-2 instances of recursive calls, generally with two pointers and two indices per call. Despite top down having a cache friendly advantage for a few levels of recursion versus bottom up passes, my comparisons have found bottom up merge sort to be 5% to 10% faster. On an Intel 3770k, 64 bit mode, sorting 20 million (20*1024*1024) 64 bit integers takes 2.07 seconds with top down, 1.92 seconds with bottom up, about 8% faster. – Madelle

For linked lists, bottom up merge sort using a small (25 to 32) array of pointers to nodes eliminates the need to scan lists to split them. For a large list with randomly scattered nodes, bottom up is 35+% faster. wiki example . – Madelle

Answer 3

I had asked the same question on coursera class forums for the 2012 August edition of this course. Professor Kevin wayne (of Princeton) replied that in many cases recursion is faster than iteration because of caching improved performances.

So the short answer that I got at that time was that top down merge sort will be faster than bottom up merge sort because of caching reasons.

Please note that the class was taught in Java programming language(not Javascript).

Corie

Better late than never comment? The caching improvement for top down could occur on small sub-arrays, where the just merged output is still in the cache to be used for the next input. However, for most processors, that cache is being flushed to memory at the same time it's being used for merge input. The end result on benchmarks I've run on X86 processors is bottom up is faster, but not by much since recursion overhead is O(log2(n)), while total time is O(n log2(n)). For example, sorting 16 million 64 bit integers on my system, bottom up takes about 1.5 seconds, top down about 1.6 seconds. – Madelle

Answer 4

As, in a bottom-up approach, we are going from a small dataset to a larger dataset for the solution while in the top-down we are continuously dividing the larger dataset to the smaller dataset for the solution.So,bottom-up merge sort tends to have better cache locality and reduced overhead due to the absence of recursive function calls. Therefore, for large datasets, bottom-up merge sort might be faster or at least more memory-efficient than the top-down approach.

Omsk

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Ramsden