4
$\begingroup$

Most libraries use some variation of bottom up merge sort, but top down merge sort seems to dominate web sites and forums.

Assume reasonably optimized implementations, where a single working array is used in addition to the original array, and copy or copy back avoided in top down merge sort by tying the direction of merge (to or from the working buffer) based on level of recursion (bottom up does this based on merge pass), then the key differences are the generation and storage of indices for runs via recursion and storage on the stack for top down versus iteration and storage possibly in registers for bottom up, and cache locality affected by the order of merge operations (top down is depth first, left first, while bottom up is breadth first).

For cache locality issues, assuming at least a 4 way set associative cache, that's enough for 2 lines for input, and 1 line for merged output, and the merge operation is a sequential operation for the 2 input runs and the merged output run. It's not clear to me if there are a few levels of recursion for top down versus passes for bottom up where top down is more cache friendly.

In all the benchmarks I've run, bottom up merge sort is faster than top down, which would explain why most libraries use some variation of bottom up merge sort. As array size increases, the relative difference decreases because most of the time is spent in a merge function that can be identical for top down and bottom up.

From a historical perspective, going back to the days of disk or tape sorts, merge sort started out as bottom up merge sort (or a variation called polyphase merge sort).

My questions are when and why top down merge sort became more popular in a classroom environment, or later on the web?


Update - I'm also wondering why bottom up merge sort seems to be so rarely seen in a classroom environment, web sites, or forum sites. My guess is that 80+% of the questions about merge sort at Stack Overflow are about top down merge sort. I only recall one question about bottom up merge sort in the last month or so.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Feb 26 '18 at 17:23
  • $\begingroup$ Our chat appears frozen; so here in comment: I've continues playing with this, and tried tuning the top-down and bottom up implementations further. I used unsafe accesses to remove some overhead and did some boring microoptimization tweaks (in the style of which function to inline when, do...while vs. while etc .); I hope the C# vs. C++ difference is small now. Indeed this appeared to help bottom-up more than top-down, which is encouraging, since vs. your C++ implementations bottom up had more catching up to do. Finally, the insertion sort cutoff size is now per-type for better generality. $\endgroup$ – Eamon Nerbonne May 21 '18 at 8:16
  • $\begingroup$ I also altered the benchmark to hopefully be more representative of real usage. It tests a variety of types (including a pointer-to-heap-allocated object), and in particular, it now tests a range of sizes; from 2^5 elements to 2^22 elements, and at each size category I dither the actual sizes to avoid measuring weird corner cases (e.g. exact multiples of 32, or conversely exact multiples of 48). Results here: github.com/EamonNerbonne/SortAlgoBench/blob/master/CSharp/… $\endgroup$ – Eamon Nerbonne May 21 '18 at 8:26
  • $\begingroup$ The short analysis being: it appears that at small sizes, there's not much difference either way (since most time is in insertion sort, that's not too surprising). But at larger sizes (92 arrays averaging 3614522.9 elements each), particularly for the heavier objects, bottom up starts falling behind. For int (per-sort working set ~32MB) the difference is small: just 0.6%. For 16-byte values it's 6%; for 48-byte values it's 10%, and for the heap-allocated values it's a whopping 25%. Even if some of that is C# vs. C++ trivia, I doubt the trend is. $\endgroup$ – Eamon Nerbonne May 21 '18 at 9:02
  • $\begingroup$ In conclusion: bottom-up appears to be simpler to implement with low-overhead, making it particularly suitable for cheap types such as plain old ints. But it's hard to have a well-balanced merge tree in a bottom up fashion, so for expensive to compare (and probably expensive to swap) types, the slight overheads of top-down matter less than the more balanced merge tree. $\endgroup$ – Eamon Nerbonne May 21 '18 at 9:04
6
$\begingroup$

Because top-down mergesort is conceptually simpler, and fits right into the curriculum of new computer scientists that learn about recursion. A small constant performance difference between top-down and bottom-up is irrelevant for its educational value.

$\endgroup$
  • 1
    $\begingroup$ @rcgldr: fit in the curriculum is for me the important aspect and dwarf any considerations about what would make easier explanation of a single thing to a total beginner. Practical examples of useful techniques like recursion and divide-and-conquer is important in a curriculum as it consolidate other aspects of the curriculum. (And I'm not sure that your consideration is that valid: take a full deck instead of 8 cards, I'll not use a bottom up approach). $\endgroup$ – AProgrammer May 11 '17 at 7:25
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Feb 26 '18 at 17:24
3
$\begingroup$

Merge sort is often paired with quicksort as the next sort algorithm after the O(n^2) sorting algorithms. This also tends to coincide with recursion as a concept.

Quick sort has to be done top down. So explaining the merge sort in the same vein (split the input and sort the parts merge after) is easier to grok.

Bottom up has much better cache performance because the cache predictor will read ahead in the array as you are iterating over the input and output arrays. In the top down you will restart often which messes up the cache predictor and the beginning of the array may have been flushed from cache at that point. It also has less random branches which means the branch predictor is also much happier.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Feb 26 '18 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.