3 ms·

An understated benefit of merge sort is that all of its access patterns have excellent locality. Regardless of big-O, this is a huge advantage because it reduce

An understated benefit of merge sort is that all of its access patterns have excellent locality. Regardless of big-O, this is a huge advantage because it reduces cache thrashing. Like it probably doesn't matter if you're sorting 10k entries, but when you're sorting several gigabytes it really does.

ErikCorry 4y ago
This is true and actually the animations probably understate it because they sort all the 4-element sections, then merge to 8-element sections etc. The actual implementation in Toit does depth first, so eg. the leftmost 8,8->16 merge is done as soon as the 8-element ranges are ready.
halayli 4y ago
Quite the opposite. Merge sort is much more susceptible to cpu cache misses. You have to go out of your way to optimize mere sort to avoid cache issues. But the devil is in the details and it really depends on the arch, the dataset you're sorting (numbers vs strings makes a big difference), cores and cache levels available, memory available.
- ErikCorry 4y ago
  In practice, to avoid worse case quadratic time, you have to have a rather involved pivot selection in Quicksort. Eg nine random or evenly distributed elements which you put in three groups of three and take the median of the median. Collecting those nine elements looks terrible for locality. Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implementing it.
  - gpderetta 4y ago
    To handle quadratic edge cases you would switch to heapsort when the recursion depth goes above the threshold. I.e. introsort; no need for convoluted pivot selection methods.
    - ErikCorry 4y ago
      That's usually called Introsort, but I think you'll find that most of these still consider at least the middle element for a pivot, so they still have a more complex cache behaviour than the naïve linear sweep from both ends of a simple Quicksort. https://en.wikipedia.org/wiki/Introsort#Implementations https://en.wikipedia.org/wiki/Introsort#Implementations And heapsort has terrible cache behaviour.
  - Laakeri 4y ago
    It's enough to just take one random element and use it as a pivot.
bee_rider 4y ago
In the rare event that you have to sort a big stack of paper, merge sort is also super intuitive and easy to apply by hand.
- dataflow 4y ago
  I like to think so but I'm not sure that's true. At least I don't think I've ever seen anyone divide a stack in half, then divide the left one in half, then divide the left one of that in half, etc. as if they're doing recursive mergesort. I feel like most people start from the first card and build upward, either with insertion sort or with something like iterative mergesort.
  - derefr 4y ago
    I think most people would shortcut the "recursive task-spawning" part by just taking all the pages and spreading them out individually side-by-side on a work surface.
    - dataflow 4y ago
      That's why I said it's like the iterative version of mergesort, which goes bottom-up. People don't divide things in half like in traditional recursive mergesort, is what I was saying.
  - bee_rider 4y ago
    What I’ve done is: Grading data structures exams (appropriately enough), I’d grab a handful of them, and grade them, and then sort the little stack. Then I’d put it aside to deal with later. Eventually I realized I was running out of desk space, so I started merging little stacks of around equal size. So the base case wasn’t 1 element, but that’s conventional for actual implementations. And the splitting wasn’t quite recursive I guess. But partial credit at least.
  - makeset 4y ago
    Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.
sakras 4y ago
Locality is good during merge but there’s no parallelism - there’s a data dependency between the previous and next iteration because we don’t know which pointer we’re supposed to advance. I think it’s still unclear whether this necessarily is compensated for by the cache locality

ErikCorry 4y ago

This is true and actually the animations probably understate it because they sort all the 4-element sections, then merge to 8-element sections etc. The actual implementation in Toit does depth first, so eg. the leftmost 8,8->16 merge is done as soon as the 8-element ranges are ready.

halayli 4y ago

Quite the opposite. Merge sort is much more susceptible to cpu cache misses. You have to go out of your way to optimize mere sort to avoid cache issues. But the devil is in the details and it really depends on the arch, the dataset you're sorting (numbers vs strings makes a big difference), cores and cache levels available, memory available.

ErikCorry 4y ago
In practice, to avoid worse case quadratic time, you have to have a rather involved pivot selection in Quicksort. Eg nine random or evenly distributed elements which you put in three groups of three and take the median of the median. Collecting those nine elements looks terrible for locality. Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implementing it.
- gpderetta 4y ago
  To handle quadratic edge cases you would switch to heapsort when the recursion depth goes above the threshold. I.e. introsort; no need for convoluted pivot selection methods.
  - ErikCorry 4y ago
    That's usually called Introsort, but I think you'll find that most of these still consider at least the middle element for a pivot, so they still have a more complex cache behaviour than the naïve linear sweep from both ends of a simple Quicksort. https://en.wikipedia.org/wiki/Introsort#Implementations https://en.wikipedia.org/wiki/Introsort#Implementations And heapsort has terrible cache behaviour.
- Laakeri 4y ago
  It's enough to just take one random element and use it as a pivot.

bee_rider 4y ago

In the rare event that you have to sort a big stack of paper, merge sort is also super intuitive and easy to apply by hand.

dataflow 4y ago
I like to think so but I'm not sure that's true. At least I don't think I've ever seen anyone divide a stack in half, then divide the left one in half, then divide the left one of that in half, etc. as if they're doing recursive mergesort. I feel like most people start from the first card and build upward, either with insertion sort or with something like iterative mergesort.
- derefr 4y ago
  I think most people would shortcut the "recursive task-spawning" part by just taking all the pages and spreading them out individually side-by-side on a work surface.
  - dataflow 4y ago
    That's why I said it's like the iterative version of mergesort, which goes bottom-up. People don't divide things in half like in traditional recursive mergesort, is what I was saying.
- bee_rider 4y ago
  What I’ve done is: Grading data structures exams (appropriately enough), I’d grab a handful of them, and grade them, and then sort the little stack. Then I’d put it aside to deal with later. Eventually I realized I was running out of desk space, so I started merging little stacks of around equal size. So the base case wasn’t 1 element, but that’s conventional for actual implementations. And the splitting wasn’t quite recursive I guess. But partial credit at least.
- makeset 4y ago
  Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.

sakras 4y ago

Locality is good during merge but there’s no parallelism - there’s a data dependency between the previous and next iteration because we don’t know which pointer we’re supposed to advance. I think it’s still unclear whether this necessarily is compensated for by the cache locality