snippetMinor
Why top down merge sort is popular for learning, while most libraries use bottom up?
Viewed 0 times
whytopwhilepopularmergelibrarieslearningbottomdownfor
Problem
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 o
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 o
Solution
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.
Context
StackExchange Computer Science Q#75216, answer score: 6
Revisions (0)
No revisions yet.