The Sound of Sorting

November 4, 2013 8:23 PM

15 Sorting Algorithms in 6 Minutes

The developers site with explanations and links to a video for each algorithm.

posted by Confess, Fletch (43 comments total)

Similarly
posted by nightwood at 8:37 PM on November 4, 2013 [1 favorite]

_____________________

Very cool.
posted by sneebler at 8:38 PM on November 4, 2013

We spent so much time on this in high school and college, and yet if I had to write a sort with a gun to my head it'd be a quick bubble sort. In real world programming we just have the database sort the damn thing. Ha!
posted by graymouser at 8:46 PM on November 4, 2013 [2 favorites]

I use merge sort for sorting graded papers.... And always always wonder if there's a better way to go.
posted by kaibutsu at 8:50 PM on November 4, 2013

HeapSort 4 EVAR. Even visually it's my favorite. Though I am charmed by bogosort's earnest derpiness. BLIP BLOOP BLOP SPLORP BLEEP BLUMP I'M TRYIN SO HARD DO YOU SEE ME DAD BLAMP BLI
posted by middleclasstool at 8:59 PM on November 4, 2013 [10 favorites]

I find this highly entertaining and sort of relaxing.

For anyone who is curious about what is going on, here is an informative video that explains different sorting algorithms.
posted by littlesq at 9:05 PM on November 4, 2013 [4 favorites]

Sorting can also sound like this.
posted by Valued Customer at 9:10 PM on November 4, 2013 [2 favorites]

This seems as good a place as any to link to Heapsort, Quicksort, and Entropy.
posted by Proofs and Refutations at 9:13 PM on November 4, 2013 [1 favorite]

I pressed play on this video and was instantly enthralled by the visuals and sound like a toddler watching Elmo. My boyfriend's response was to silently toss me a pair of earphones and shoot me an annoyed glare.
posted by tepidmonkey at 9:40 PM on November 4, 2013 [4 favorites]

As was pointed out to me, Andrut's video is again not the first sound generator for sorting algorithms. The old QBasic produced by Microsoft in 1991 also contained a sorting demo program with audibilization

Which reminds me of CSIRAC and Ferranti Mark 1, which had execution audibilization in the 1950s, not as a novelty per se, but for debugging programs. They of course used it to play music.
posted by zamboni at 9:53 PM on November 4, 2013

graymouser: "We spent so much time on this in high school and college, and yet if I had to write a sort with a gun to my head it'd be a quick bubble sort. In real world programming we just have the database sort the damn thing. Ha!"

Kind of sad, because merge sort is pretty simple, obvious and generally as fast as quicksort.
posted by pwnguin at 10:01 PM on November 4, 2013 [2 favorites]

littlesq: really really great video. Thanks.
posted by lkc at 10:26 PM on November 4, 2013

Loved it. When they went to Bubble sort I noticed that the columns got thicker — "Oh, that's nice, they're shrinking the field and letting the second squad get some play time."
posted by benito.strauss at 10:40 PM on November 4, 2013 [1 favorite]

This was like dessert for my OCD, thanks!
posted by quazichimp at 10:40 PM on November 4, 2013 [1 favorite]

And for what it's worth, I think the LSD Radix sort is what it's going to sound like when the robots decide to band together and attack us: initially a ball of confusion, and then waves of organization spread wider and wider, until they are all one perfectly organized vector heading right into humanity's heart.
posted by benito.strauss at 10:51 PM on November 4, 2013 [2 favorites]

Also, here is one of Timsort.
posted by lkc at 11:07 PM on November 4, 2013

Sometimes YouTube comments are comedy gold.

Honestly, I have no idea what the fuck is going on.
posted by crapmatic at 12:57 AM on November 5, 2013 [1 favorite]

It's cool how you can just simply see the insertion sort's 0(n^2) performance. Very neat video.

I also love the bogosort ending, it sounds like it is stupid...as it is. Hilarious.
posted by dubitable at 1:42 AM on November 5, 2013

Using high-level languages only, and therefore just letting sort() take care of stuff, I always forget that this goes on underneath. In the real world, do these different methods exist just as historical legacies and in practice everyone uses the current fastest one? Or do they differ so much in memory requirements that people choose according to task and target architecture?
posted by cromagnon at 2:10 AM on November 5, 2013 [1 favorite]

They are used in different cases, of which the fastest are:

Radix sort is linear, but only works on integral data.

Introsort is fastest on arbitrary data when you consider typical memory caching.

Merge sort is a fast stable sort (equal elements retain their original order).

Timsort is fast when the input is almost sorted.

Heap sort requires no additional memory (it is in-place).

Bitonic sort is O(log^2 n) given a parallel architecture (like a graphics card).

posted by esprit de l'escalier at 2:25 AM on November 5, 2013 [7 favorites]

Bubble sort not bubbly enough.
posted by pracowity at 2:30 AM on November 5, 2013

Bogo sort is always the fastest ( O[1] ) if you don't care if your data is actually sorted.
posted by tehloki at 2:30 AM on November 5, 2013 [5 favorites]

Timsort is fast when the input is almost sorted.

More than that, Timsort is designed to work extremely well when there are large "runs" of already sorted sublists in the data, which is very common for real world data a computer program might want to sort. Say, for instance, if you have ten already sorted lists of people that you wish to turn into one big list of sorted people, you can just append the lists one after another, and then sort it. Most sorting algorithms will take just as long to sort this as a totally random list, even though large parts of it is already sorted. Timsort, on the other hand, will recognize the already sorted bits and merge them, similar to how the merge pass in merge sort works. This is why it's starting to become one of the more popular library sorting functions, being the default sorting algorithm of both Python and Java.
posted by gkhan at 4:49 AM on November 5, 2013

In my experience, the only time sorting is much of a real performance issue is when someone chose the wrong STL container for the job.
posted by Foosnark at 5:17 AM on November 5, 2013 [1 favorite]

This looks and sounds so much like an end-of-level points tally from some 1980s video game.
posted by RonButNotStupid at 5:52 AM on November 5, 2013 [1 favorite]

This video would be even better if it included a couple of lines of text about tradeoffs/usage of each type of sort. (like esprit's comment)

(oh, and how does threading help/hurt these things? Do the answers change if you have a list of 20 million integers and access to 2, or 200 cores? )

I should have never dropped out of college. (Though in MY day, we didn't have all these fancy multicores and terabytes of memory)
posted by DigDoug at 5:55 AM on November 5, 2013

Yeah, I want this Wikipedia comparison table but not written for CS majors.
posted by DigDoug at 5:57 AM on November 5, 2013

My new favourite stupid sorting algorithm is sleep sort, as presented by the ever-inventive guys at 4chan:
https://dis.4chan.org/read/prog/1295544154
posted by cyberscythe at 6:06 AM on November 5, 2013 [4 favorites]

Loved the sound and color effects. :)
posted by gemutlichkeit at 6:07 AM on November 5, 2013

(oh, and how does threading help/hurt these things? Do the answers change if you have a list of 20 million integers and access to 2, or 200 cores? )

In part, yeah. Merge sort and quick sort are both amenable to being parallelized since they both operate recursively on non-overlapping list segments.
posted by invitapriore at 7:02 AM on November 5, 2013

Notice that the number of array items isn't identical for all the examples and the delay factor is different for the algorithms, so it is hard just from observation to say that one algorithm is better than another. They normalized the data set and delay for the audio but I think it does a good job of illustrating how the different methods work through the data.
posted by dgran at 7:11 AM on November 5, 2013

Sometimes I wish I wasn't just a high-level language business programmer with a biology degree, because this is fascinating and a great visualization (the music helps me since I'm very musically inclined).

In my day-to-day (C#) I just do

int[] someArray = new int[5] { 8, 10, 2, 6, 3 };
Array.Sort(someArray);

It uses QuickSort and is unstable which I believe means that the order of equal items might not be preserved.
posted by freecellwizard at 7:51 AM on November 5, 2013 [1 favorite]

I kind of want to write some experimental DSP code that just takes the incoming audio buffer and starts to sort it according to the selected algorithm, with a parameter for how far it's allowed to go. Some limits to prevent it falling behind. Maybe in fixed sized batches, or maybe group them by zero crossings.

I'm sure it would sound horrible, and I can't wait to run a kick drum loop or a guitar part through it.
posted by Foosnark at 8:31 AM on November 5, 2013

kaibutsu: "I use merge sort for sorting graded papers.... And always always wonder if there's a better way to go."

Unless you're grading more than 10 million papers... no. Everything else would require more time to write than it would save you in time.

(So did typing your comment, BTW.)
posted by IAmBroom at 9:09 AM on November 5, 2013 [1 favorite]

I sat there for six minutes with my jaw hanging open. That's beautiful.

It's been so, so long since CS101/102, and that was the last time I saw any of these, and by no means had I seen all. ... is Radix Sort magic?
posted by seyirci at 9:29 AM on November 5, 2013

seyirci: "... is Radix Sort magic?"

Nah, long story short is that it uses the key you're sorting on to stick the item in the right place, iterating over the keys once for each digit place. Since it's not a comparison sort it can beat out the usual n * log n lower bound, but it assumes that the key is or can be represented as an integer. The cool thing is that it works quite simply for positive floats, since in IEEE754 relative ordering is preserved between the float and integer representations of a given bit pattern (when the float is negative it's reversed, which you have to account for if you want your floating point radix sort to work across your entire input space).
posted by invitapriore at 11:53 AM on November 5, 2013

I poked around Wikipedia after watching this, now I'm amazed by how much I don't know about sorting. Smoothsort? Judy trees? Apparently there's been a lot of activity taking place here since I declared my fealty to heapsort decades ago.
posted by fredludd at 12:13 PM on November 5, 2013

Also I feel compelled to mention whenever this topic comes up just how much an imperative formulation obscures the basic nature of quicksort. Witness, in Haskell:

quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = (quickSort $ filter (<=x) xs) ++
                   [x] ++
                   (quickSort $ filter (>x) xs)

Or in Clojure:

(defn quicksort [[x & xs :as all]]
  (if (seq all)
    (concat (quicksort (filter #(<= % x) xs))
            [x]
            (quicksort (filter #(> % x) xs)))))

It's a naive implementation that'll blow up the stack pretty quickly and ignores the finer points of pivot selection and equality handling between list elements and the pivot, but as a demonstration of the basic framework of the algorithm it communicates what's happening so much more straightforwardly than any didactic imperative implementation I've seen.
posted by invitapriore at 1:07 PM on November 5, 2013 [2 favorites]

Or, a slightly more fun Clojure version, because juxt is fun:

(defn quicksort [[x & xs :as all]]
  (if (seq all)
    (let [[lte gt] ((juxt filter remove) #(<= % x) xs)]
      (concat (quicksort lte) [x] (quicksort gt)))))

posted by invitapriore at 1:19 PM on November 5, 2013

Step 1: Learn Haskell
Step 2: Marvel at how much easier quicksort is to understand
posted by smackfu at 2:41 PM on November 5, 2013 [6 favorites]

Sorting can also sound like this.

The algorithm would have been more efficient without the music and folk dancing.
posted by popcassady at 3:01 PM on November 5, 2013

smackfu: "Step 1: Learn Haskell
Step 2: Marvel at how much easier quicksort is to understand"

Aw. It really is just another language for the most part,* assuming you're familiar with the functional idiom. The fact that they use mathematical terminology to describe concepts in the type system obscures the reality that those concepts are really useful and pretty easy to grasp. I had a harder time coming to grips with the semantics of JavaScript than I did with Haskell, to be honest, although I'm still just a beginner at the latter.

* Although you wouldn't necessarily know it from browsing community resources... I remember laughing ruefully after subscribing to the Haskell beginner's digest recently and the first email I got was headlined with the topic "Constrained polymorphic functions as natural transformations."
posted by invitapriore at 9:58 AM on November 7, 2013 [3 favorites]

It's a naive implementation that'll blow up the stack pretty quickly and ignores the finer points of pivot selection and equality handling between list elements and the pivot, but as a demonstration of the basic framework of the algorithm it communicates what's happening so much more straightforwardly than any didactic imperative implementation I've seen.

Awesome. This sort of stuff is why cavemen had to invent wizards.
posted by cromagnon at 2:19 PM on November 8, 2013