Sorting algorithms that don’t hate you

https://medium.com/@erik_68861/sorting-algorithms-that-dont-hate-you-165ba313bbc2

by tosh • 4 years ago

145 82 4 years ago

medium.com

ErikCorry14• 4 years ago

I had way too much fun making these animations.

kasperl• 4 years ago

I find it strangely mesmerizing to watch sorting algorithms do their thing. Thanks for having fun!

otherfiftycents• 4 years ago

What software did you use to make these animations?

ErikCorry14• 4 years ago

I hacked it up in Toit :-)

Not the prettiest code, but it's in the examples directory at https://github.com/toitware/toit-png-display if anyone cares.

marginalia_nu• 4 years ago

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.

ErikCorry14• 4 years 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• 4 years 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.

ErikCorry14• 4 years 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.

bee_rider5• 4 years 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.

dataflow2• 4 years 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.

dhosek• 4 years ago

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.

HelloNurse• 4 years ago

Merging stacks of papers by hand isn't the same as exchange-based computer mergesort: if the cost of inspecting and comparing items is negligible relative to actually moving them the basic, unit cost operation is splitting a sequence into three possibly empty sequences and splicing the middle piece into an arbitrary position in another sequence. In some cases reversing the spliced sequence is free ("pancake" sorting).

This cost model is an important reason to merge bottom up, from sorted subsequences, without arbitrary splitting that can add work but not reduce it.

somat• 4 years ago

At one point I used to work at a place that had a production process that used several hundred ibm 3480(if I remember correctly) tape cartridges. I would do a LSB radix sort afterwards to get them back in order.

I think back on it with a certain amount of nostalgia now, but it was a stupid way to do operations, even at the time, They had invested big in computers in the 70's and were still maintaining the same tech stack in the early 00's when I worked there.

sakras• 4 years 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

olliej3• 4 years ago

I 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.

ErikCorry14• 4 years ago

If 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.

olliej3• 4 years ago

What 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.

wging• 4 years 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/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?)

loeg• 4 years ago

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.

ErikCorry14• 4 years ago

TIL.

chrchang5232• 4 years ago

Note 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-Xii5• 4 years ago

Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.

chrchang5232• 4 years ago

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.

bee_rider5• 4 years ago

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).

mxkopy• 4 years ago

I'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.

ErikCorry14• 4 years ago

Well these are the sorts of arguments I made on the V8 bug, and people were not happy.

lucumo2• 4 years ago

No, there could be unsortable properties that are nonetheless different. Or the use case could really require that the original order is relevant.

But yeah, I don't usually need stability either.

CipherThrowaway• 4 years ago

Deeper comparison doesn't solve the problem because input order is arbitrary. The order may be based on a user dragging items around in a list widget, for example.

The easiest way to transform an unstable sort into a stable sort is probably mapping input from T -> (Index, T) and including the index as a sort key.

noitpmeder• 4 years ago

And if they're not completely equal?

tgv• 4 years ago

I'll spell it out then: you don't always need to sort based on the entire object's value. Comparing the whole object can be pretty expensive when you only need to sort by one field.

schneems• 4 years ago

I wish Ruby had stable sort By default.

srcreigh• 4 years ago

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.

smusamashah• 4 years ago

I made a sorting algorithm visualizer some time ago https://xosh.org/VisualizingSorts/sorting.html You can put in your own algo and share it via url.

orlp5• 4 years ago

At 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.

Perhaps the V8 people will be interested in it as well.

ErikCorry14• 4 years ago

Cool stuff.

Is Glidesort1024 still stable?

orlp5• 4 years ago

Yes, it is.

Traubenfuchs• 4 years ago

Those 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#?

orlp5• 4 years ago

For 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• 4 years ago

Wow, this looks very impressive.

I thought that sorting algorithms were at a culminating point, but it appears this is not the case at all.

dgacmu• 4 years ago

I've been interested in this since your presentation in May; any plans to release the source any time soon?

(Here's where I hope I'm asking a dumb question and you already have, but I haven't been able to find it.)

orlp5• 4 years ago

Hey, the open source release will coincide with the FOSDEM presentation, so in a little under three weeks it will be under my Github account github.com/orlp.

adgjlsfhk12• 4 years ago

How does the speed compare to a well optimized radix sort?

orlp5• 4 years ago

I haven't compared because they're apples and oranges. The radix sorts do not allow a custom comparison function.

I would assume that they're faster, especially if using SIMD.

graycat5• 4 years ago

Let 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?

thomasmg2• 4 years ago

I 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).

graycat5• 4 years 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

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.

graycat5• 4 years ago

     '    Function obj_heap_insert

     '    Object heap insert to use the heap algorithm to maintain
     '    a 'priority queue'.
     '
     '    So, suppose for positive integer n we have x(i) for i =
     '    1, 2, ..., n and for positive integer m <= n we want the
     '    m largest of the x(i).  So, we allocate an array y(j), j
     '    = 1, 2, ..., m.
     '
     '    Suppose we regard y as an ascending heap, e.g., so that
     '    y(1) <= y(j), j = 2, ..., k <= m where the number of
     '    locations of y in use so far is integer k where 0 <= k <=
     '    m.
     '
     '    Then for i = 1, 2, ..., n, we consider inserting x(i)
     '    into the heap.
     '
     '    If k < m, then we set k = k + 1 and set y(k) = x(i) and
     '    'sift' to 'promote' the value in y(k) until we have a
     '    heap again.
     '
     '    If k = m, then we compare x(i) and y(1).  If x(i) <= y(1),
     '    then we are done with x(i).  Else, x(i) > y(1) and y(1) is
     '    not among the m largest and, to 'remove' value y(1) we
     '    set y(1) = x(i) and 'sift' the value in y(1) to create a
     '    heap again.
     '
     '    After i = n, y contains the m largest of x(i), i = 1, 2,
     '    ..., n.
     '
     '    The advantage of this routine is speed:  When k = m, the
     '    effort to insert x(i) is proportional to log(m).  When k
     '    < m, the effort to insert x(i) may be proportional just
     '    to k.  The worst case would be when the array x was in
     '    ascending order since then x(i) would have to be inserted
     '    for each i.  Similarly, in the case the array x is in
     '    descending order, after m inserts, no more inserts will
     '    be done.  For the order of array x 'random', once a
     '    relatively large fraction of the m largest are in the
     '    heap, additional inserts become relatively rare.
     '
     '    This routine is to be 'polymorphic', that is, to work for
     '    essentially any user defined class my_class1 where
     '
     '         Dim m, n As Int32
     '         Dim x( n ) As my_class1
     '         Dim y( m ) As my_class1
     '
     '    This routine can build an ascending heap, as discussed
     '    above, or a descending heap.  The only difference is how
     '    the comparisons are made in the class used for the
     '    interface.
     '
     '    The interface IComparer is used.  If the usual class
     '    Comparer is used for this interface, then this function
     '    builds an ascending heap, that is, where upon return
     '
     '         y( 1 ) <= y( j ),
     '
     '    for j = 2, 3, ..., m.

         Function obj_heap_insert( _
           x As Object, _
           y() As Object, _
           ByRef k As Int32, _
           m As Int32, _
           compare As IComparer) As Int32

         Dim routine_name As String = "obj_heap_insert"

         Dim error_code As Int32
         Dim return_code As Int32 = 0
     '   Dim result_code As Int32
         Dim message_tag As Int32

         Dim i_father As Int32
         Dim i_child0 As Int32
         Dim i_child1 As Int32
         Dim i_child2 As Int32
         Dim i_2 As Int32 = 2

         Try

         error_code = 1001

         message_tag = 1001
         If console_msg_level >= console_routine_messages2 Then _
           Console.WriteLine( routine_name & " " & message_tag & _
             ":  Started ..." )

         error_code = 1002

         If m <= 0 Then
           return_code = 1001
           Goto out
         End If
         If k < 0 Then
           return_code = 1002
           Goto out
         End If
         If k > m Then
           return_code = 1003
           Goto out
         End If
         If y.GetUpperBound(0) < m Then
           return_code = 1004
           Goto out
         End If

         error_code = 1003
         If k < m Then

           i_child0 = k + 1
           k = i_child0
           error_code = 1004
           Do      ' Sift value of x into correct position.
             If i_child0 < 2 Then Exit Do
             i_father = i_child0 \ i_2
             error_code = 1005
             If compare.Compare( x, y( i_father ) ) >= 0 Then Exit Do
             y( i_child0 ) = y( i_father )
             i_child0 = i_father
           Loop    ' Sift value of x into correct position.
           error_code = 1006
           y( i_child0 ) = x
           Goto out

         End If

         error_code = 1007
         If compare.Compare( x, y( 1 ) ) <= 0 Then Goto out

         i_father = 1

         error_code = 1008
         Do        ' Delete value of y( 1 ) and sift x to correct position
                   ' starting at location y( 1 )
           If i_father > m \ i_2 Then Exit Do
           i_child1 = i_father + i_father
           If i_child1 < m Then
             i_child2 = i_child1 + 1
             error_code = 1009
             If compare.Compare( y( i_child1 ), y( i_child2 ) ) < 0 Then
               i_child0 = i_child1
             Else
               i_child0 = i_child2
             End If
           Else
             i_child0 = i_child1
           End If
           error_code = 1010
           If compare.Compare( x, y( i_child0 ) ) <= 0 Then Exit Do
           y( i_father ) = y( i_child0 )
           i_father = i_child0
         Loop      ' Delete value of y( 1 ) and sift x to correct position
                   ' starting at location y( 1 )
         y( i_father ) = x

         Catch

           Console.WriteLine( " " )

           message_tag = 1002
           Console.WriteLine( routine_name & " " & message_tag & _
             ":  Error condition raised. " & vbCrLf & _
             ":  error_code = " & error_code & vbCrLf & _
             ":  err.number = " & err.number & vbCrLf & _
             ":  err.source = " & err.source & vbCrLf & _
             ":  err.description = " & err.description )

           message_tag = 1003

           Console.WriteLine( routine_name & " " & message_tag & _
             ":  Raising error condition with error_code = " & error_code )

           err.raise(error_code, routine_name)

         End Try

       out:

         message_tag = 1004

         If console_msg_level >= console_routine_messages2 Then _
           Console.WriteLine( routine_name & " " & message_tag & _
             ":  Returning." )

         Return return_code

       End Function     ' Function obj_heap_insert

sorokod3• 4 years ago

Dart's default sort is not stable either.

floitsch• 4 years ago

That's probably on me...

If I had to do it again, I would make it stable now.

ErikCorry14• 4 years ago

Luckily this is a backwards-compatible change so sorokod should lobby the Dart team.

ilyt2• 4 years ago

Aside 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

sorokod3• 4 years ago

Non stable sorts are very annoying and confusing in UI. I'd argue that in most cases you'd want a stable one.

ilyt2• 4 years ago

Right, which is why I said it's fine as long as there is stable option, but I don't write UIs

xpe• 4 years ago

The code examples are written in Toit:

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.

SideQuark• 4 years ago

Any 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.

Sorting algorithms that don’t hate you

Related Stories