Sorting algorithms that don’t hate you
medium.com
Sorting algorithms that don’t hate you
1–10 of 84 posts
Re: Sorting algorithms that don’t hate you
#2I had way too much fun making these animations.
Re: Sorting algorithms that don’t hate you
#3An 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.
Re: Sorting algorithms that don’t hate you
#4I had way too much fun making these animations.
I find it strangely mesmerizing to watch sorting algorithms do their thing. Thanks for having fun!
Re: Sorting algorithms that don’t hate you
#5An 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.
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.
Re: Sorting algorithms that don’t hate you
#6I am curious about exactly what v8 was doing at the time, because "just use Quicksort" doesn't work for inconsistent comparison functions or mutating data. These issues aren't magically resolved with "use a stable sort", but it means you're not just calling qsort(...) to perform the sort.
I vaguely recall JSC actually having a literal tree sort at one point to deal with this.
Re: Sorting algorithms that don’t hate you
#7> Recently, Timsort has become popular, also a variation of Merge Sort. However, Timsort was not invented yet in 2008.
Timsort is from 2002. Not sure where this comes from. Perhaps it wasn't as popular or widely known in 2008 as it is now, but I actually learned about it at about that time. See also:
https://mail.python.org/pipermail/python-dev/2002-July/02683...
(edit: timsort was introduced to Java in 2009, per https://bugs.openjdk.org/browse/JDK-6804124, and knowledge of it would probably have spread much further from that point, so maybe that's the source of confusion?)
Re: Sorting algorithms that don’t hate you
#8Note that it is straightforward to modify an unstable sort algorithm into a stable one, when it’s okay to use O(n) extra memory: define an array that tracks each element’s original position, and when two elements otherwise compare equal, use the original position as the final tiebreaker.
(With that said, Timsort must be faster in practice than this kind of retrofitted unstable sort. I’m curious how large the difference is.)
Re: Sorting algorithms that don’t hate you
#9I wish Ruby had stable sort By default.
Re: Sorting algorithms that don’t hate you
#10An 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.
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.