6 ms·
Sorting algorithms that don’t hate you
- ErikCorry 4y agoI had way too much fun making these animations.
- kasperl 4y agoI find it strangely mesmerizing to watch sorting algorithms do their thing. Thanks for having fun!
- otherfiftycents 4y agoWhat software did you use to make these animations?
- ErikCorry 4y agoI hacked it up in Toit :-) Not the prettiest code, but it's in the examples directory at https://github.com/toitware/toit-png-display https://github.com/toitware/toit-png-display if anyone cares.
- marginalia_nu 4y agoAn 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 agoThis 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 agoQuite 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 agoIn 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 agoTo 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 agoThat'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 agoIt's enough to just take one random element and use it as a pivot.
- bee_rider 4y agoIn 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 agoI 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 agoI 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 agoThat'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 agoWhat 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 agoBecause without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.
- sakras 4y agoLocality 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
- olliej 4y agoI 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.
- ErikCorry 4y agoIf you provided an inconsistent comparison function I don't see how it's the sort implementation's responsibility to produce a sensible output. Or even to terminate at all.
- olliej 4y agoWhat are you talking about? This is in a JS engine, where by design all code is untrusted. If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.
- ErikCorry 4y agoObviously it may never crash, and it never did, even with a bad comparison function. But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that? Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in the middle of sorting, which could move the array.
- olliej 4y agoPrior to chrome every browser had a “terminate js after x seconds” option that didn’t mean “kill the process”. But the point is that the general quicksort algorithm does a bunch of unsafe memory accesses if the comparator is unstable (either directly or by modification of the sorted data). As demonstrated by every qsort implementation going wrong in unsafe ways in such a scenario. Now maybe you used a version of qsort that actually made sure it wasn’t going out of bounds and what not and did … something? When that occurred, and saying what that something was would be a reasonable answer. As for qsort() not being an option due to gc, that’s only a problem due to v8’s gc - JSC for instance could just use qsort or what not if it was sure the sort was consistent.
- wging 4y ago> 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/026837.html 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 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?)
- chrchang523 4y agoNote 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.)
- hypertele-Xii 4y agoIsn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.
- chrchang523 4y agoThat'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.
- bee_rider 4y agoThis 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).
- mxkopy 4y agoI'd assume cache locality makes it worthwhile, especially if the keys are big, point to big things that need to move, or live on separate drives. To that last point I'd wager stable algorithms can imply parallelization.
- ErikCorry 4y agoWell these are the sorts of arguments I made on the V8 bug, and people were not happy.
- lucumo 4y ago
- schneems 4y agoI wish Ruby had stable sort By default.
- srcreigh 4y agoI 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.
- smusamashah 4y agoI made a sorting algorithm visualizer some time ago https://xosh.org/VisualizingSorts/sorting.html https://xosh.org/VisualizingSorts/sorting.html You can put in your own algo and share it via url.
- orlp 4y agoAt FOSDEM 2023 I will be presenting glidesort in the Rust room. It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra memory. It is 11.5x faster if you happen to sort only 4096 distinct integers with many duplicates. Note that the algorithm is purely comparison based and does not contain special type-dependent SIMD stuff. I have a short preliminary talk on glidesort here: https://www.youtube.com/watch?v=2y3IK1l6PI4 https://www.youtube.com/watch?v=2y3IK1l6PI4. Perhaps the V8 people will be interested in it as well.
- ErikCorry 4y agoCool stuff. Is Glidesort1024 still stable?
- orlp 4y agoYes, it is.
- Traubenfuchs 4y agoThose numbers look impressive. For stuff like this, can it be said that it should just be implemented as is in the std libs of mainstream languages like Java, Python, C#?
- orlp 4y agoFor C#, it is very similar to Rust, so I would say yes. I'm too unfamiliar with the JVM and its performance characteristics to say for sure for Java, but probably also yes. However, the performance characteristics of Python are so different to Rust that I think it's safe to say a different approach will likely end up better (one that focuses on minimizing indirections and comparison function invocations).
- xeyownt 4y agoWow, this looks very impressive. I thought that sorting algorithms were at a culminating point, but it appears this is not the case at all.
- graycat 4y agoLet n be a non-negative integer. A number n is bit reversed if it is written was written in binary (base 2) and then the bits were written in reverse order. Last time I looked at Shell sort, when sorting n records on keys in bit reversed order, the iterations of Shell sort did nothing until the last iteration at which time Shell sort was just bubble sort or some such and, whatever, ran in time O(n^2) where the O() is some obscure but now common notation. The article claims something smaller than O(n^2). Okay, but to get something smaller, have to tweak what used to be a standard version of Shell sort. For another point, the article wants a stable sort -- if two records (the data being sorted) A and B have equal keys and before the sort record A is before record B, then after the sort record A will still be before record B. But, if want a stable sort, then for one approach, before the sort, number the records and use these numbers as part of the keys. Right this extra step runs in time O(n) and uses extra temporary, working storage proportional to n. For current computing, is this extra storage a meaningful issue?
- thomasmg 4y agoI wonder which type of Shell sort you were looking at. In my experience, it is fairly simple to implement gap sequence that is faster than O(n^2). Sure it is not a stable sort. But it is really simple (a few lines of code), doesn't use recursion, and is fairly fast. In fact, I'm not aware of an algorithm that is as simple as Shell sort, and at the same time much faster than O(n^2).
- graycat 4y ago> In fact, I'm not aware of an algorithm that is as simple as Shell sort, and at the same time much faster than O(n^2). My favorite is heap sort, guaranteed O(n log(n)) average case and worst case, meets the Gleason bound and, thus, is the fastest possible sort based on comparing pairs of keys (in one of volumes of D. Knuth, The Art of Computer Programming). You mentioned simple: The logic of the heap data structure and its corresponding code seem to be relatively simple. Of course, radix sort does not work by "comparing pairs of keys", may be regarded as O(n), and, check this, may also be stable. Of course, radix sort was the algorithm of the IBM punched card sorting machine so maybe goes back to before 1900 and, thus, is likely the oldest of the common sorting algorithms. Below (in a separate post) is code for ai_heap_sort02 which is an (ascending integer) heap sort routine. Right, this code is for only ascending, integers, and arrays and, thus, is far from the practice of generic code, e.g., as in https://en.wikipedia.org/wiki/Generic_programming https://en.wikipedia.org/wiki/Generic_programming The advantages of generic code my work doesn't really need. Once I wrote some generic code, and that experience was enough! The code is in Microsoft's Visual Basic .NET. Why Visual Basic .NET? I have written some C code. There are claims that the programming language C has idiosyncratic syntax. Whatever it has, I don't like its syntax. I.e., supposedly i = ++j+++++k++ is legal -- increase j and k by 1, add the results, assign the result to i, and then increase j and k by 1 again -- but when I tested this on two different C compilers I got different results. If the compilers can't agree on the syntax, I don't want to try to understand it! Besides, C is supposed to be really simple, close to assembly language, and highly portable, and ambiguity I observed for i = ++j+++++k++ conflicts with those attributes! Besides, that syntax gets the grand prize for not just idiosyncratic but obscure, ugly, outrageous, etc.! Maybe C and C++ are essential for Windows internals and for Windows applications that make direct use of the System32 API, but I've never written such code since my background is applied math software. Thus, also I don't like the related syntax of C++ or C#. The syntax of Visual Basic .NET (VB) is more traditional, more like the original Basic, then Fortran, Algol, Pascal, and PL/I (maybe my favorite). Thus, VB is relatively easy to teach, learn, read, and write, and these attributes might be considered important in a large project! Whatever the syntax of VB is, there are claims that VB and C# have equivalent semantics and differ only in syntactic sugar. I.e., supposedly there is a source code translator program than can translate code in either of VB or C# to the other. So, for my project, code to run on Windows, I am writing in VB instead of C#. Also below (in a separate post) is code Function obj_heap_insert Here I use the heap data structure, the main idea in heap sort, to maintain a priority queue. So, with this code can look at 20 million objects one at a time and end up with, e.g., the 20 largest. Uh, how else to do that???!!! Right, this code starts to be a little big generic. Right, operating on the heap data structure can hurt possibly desired main memory and cache memory locality of reference, but there is at least one modification of modifying operations on a heap that speed up what otherwise might be the case of a heap large enough to need virtual memory. All this code appears to run correctly. I have later versions modified, longer, less easy to read, to use an error handling technique I cooked up -- really simple, I wouldn't recommend for large projects and it will likely become a case of technical debt if my work grows a lot! Uh, my view, a judgment call, is that the article and my post here go deeper into sorting than we should. I want to declare sorting as a plenty well enough understood, solved problem and move on to other challenges.
- sorokod 4y agoDart's default sort is not stable either.
- floitsch 4y agoThat's probably on me... If I had to do it again, I would make it stable now.
- ErikCorry 4y agoLuckily this is a backwards-compatible change so sorokod should lobby the Dart team.
- sorokod 4y agoIs it though? Or is Dart-Js not a thing any more? https://github.com/dart-lang/sdk/issues/433#issuecomment-108303817 https://github.com/dart-lang/sdk/issues/433#issuecomment-108...
- ErikCorry 4y agoDart2JS is still a thing, but sort in JS is stable now since 2019 so DartVM should make theirs stable to stay compatible with Dart2JS.
- ilyt 4y agoAside from some test code being sometimes annoying why people care ? I'd be perfectly fine with just having to call StableSort vs Sort once in blue moon when I need it
- xpe 4y agoThe code examples are written in Toit: https://toitlang.org/ https://toitlang.org/ > Toit is a modern high-level language designed specifically for microcontrollers > Toit is optimised for live reloading on your microcontroller. Your code runs incrementally as you write it and you get instant feedback. Push changes over your local WiFi in two seconds and reserve your USB cable for charging your phone. You iterate quickly, learn fast, and build better things.
- daniel-cussen 4y ago[dead]
- SideQuark 4y agoAny comparison based sorting algo can be made stable. Consider position as a tie breaker. Most can be done in place with some effort. Then you need to worry not about asymptotics, but the constant factors. Quicksort has significantly lower operation count than heap sort, even though both are O(nlog n). For small numbers bubble sort is quicker than both (and many good sorts leverage this via hybrid methods). Caches add another massive game changing performance dial to fiddle with. Taking stock at this level, ignoring that many of the non-green field he chose can be made green, misses important nuance.