I didn't expect to learn something new about sorting while reading this. It's really cool that you can do Merge Sort asymmetrically, which lets you use a scratch buffer only 1/4 the size of the original array.
Sorting algorithms that don’t hate you
11–20 of 84 posts
Re: Sorting algorithms that don’t hate you
#12I had way too much fun making these animations.
What software did you use to make these animations?
Re: Sorting algorithms that don’t hate you
#13Note 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 differen…
Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.
Re: Sorting algorithms that don’t hate you
#14An 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.
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.
Re: Sorting algorithms that don’t hate you
#15Note 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 differen…
Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.
That's my usual approach, but there are clearly some programmers who don't want to always do this, and sometimes a stable-sort library function does in fact allow them to be more productive.
Re: Sorting algorithms that don’t hate you
#16An 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.
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.
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.
Re: Sorting algorithms that don’t hate you
#17Note 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 differen…
Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.
This seems basically equivalent to saying that whether or not a sort is stable is irrelevant, right? If the position of elements with equal keys doesn’t matter for your application, then of course there’s no reason to use a stable sort (or convert a non-stable one to stable by whatever trick).
Re: Sorting algorithms that don’t hate you
#18An 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.
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.
When I taught, I would sort graded papers/tests using quick sort. Put all the a–l in on pile and m–z in the other, then do each pile into halves and manually sort the quarters. And since I knew what the sorted set looked like, finding pívot points was trivial.
Re: Sorting algorithms that don’t hate you
#19> 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 htt…
I used Timsort in a class around 2010 and it had been in Python for “a long time” at that point. I also tripped on this article’s claim that it didn’t exist yet in 2008.
Re: Sorting algorithms that don’t hate you
#20Earlier quoted context omitted.
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.
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.
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.