Image by Christian St-Marseille from Pixabay
It is a strange place to start a conversation by saying the "music" of sorting algorithms appeals to the same sense of order from chaos that allowed J.S. Bach's children to wake him up with a nearly-played scale that he would then finish, but then have to say in the same sentence: SEIZURE and VOLUME warning! Sorting algorithms need to be approached with respect for what they are like, and respect for your own sensory limits. They are bright and loud and high-pitched in general, AND, as we will see, they will sneak in other WARNED types of tones in on you ... so proceed with respect!
From less complex to more complex ... let's just start by saying that videos of sorting algorithms are ways to demonstrate what computers use to manage information with sight and MIDI sounds. Honorable mention is given to impractical sorts that are fun to watch and listen to, but no programmer would ever use in real life. Ironically, some of the slowest sorts are showed more love musically than some of the fastest ones ... this one here reminds me of Bach and also Latin Jazz taking a walk together on the atonal side ... there are flashes of bits of melody that are almost recognizable in here ...
... and one of the reasons we get to pick them up is that this video creator took his favorite minute from this particular sort and looped it for an hour. He might as well have done that. Bogo Sort, which basically looks at an array of numbers, checks to see if it is sorted, and if not, scrambles it and checks it again. It actually does no sorting, just checking ... and that means that EITHER Bogo Sort is going to get it right randomly at some point, or keep checking on an array of numbers this size until the heat death of the universe. It is a disaster of a program ... but it is still much beloved, and is often among the most musical of sorts (that don't sort), because within the chaos that is not going to be fully resolved, Bogo Sort provides beautiful moments when the right MIDI work is done. I can leave this one on in the background of, say, writing this whole post, and enjoy it.
By contrast, Silly Sort and Slow Sort both sound like an disaster in progress that will only get saved at the very end ... although your career couldn't be saved if you programmed either one of these. They are often programmed MIDI-wise to let you know: "It's not obvious at first, but DON'T USE THESE." Slow Sort can make the point for both itself and its equally silly companion. Don't be fooled by the pretty colors (that we'll get back to in a better context later), and understand: once you have heard the first minute, you will understand the answer to the question: "Just how bad is Slow Sort?"
And then, there is Stooge Sort ... faster than Bogo, Slow, or Silly, but just with a real passion for checking its work ... it has all the charm in computer science of watching the small whirlwinds whistle and wind across the great desert plains of the U.S. Southwest ... harmless, seemingly aimless, around and around, back and forth, but nonetheless moving forward with their associated weather systems. Somebody has got to get the tumbling tumbleweeds where they need to go. Stooge Sort is the hero nobody asked for, but the tumbleweeds needed.
Moving up the efficiency scale from Stooge Sort but still not quite at efficiency, here is another of my highly musical favorites -- if Stooge Sort is the desert whirlwind, Napoleon Sort is the D-Mixolydian scale summer thunderstorm. You will hear the wind blowing mightily and the rain pouring down, and feel the thunder shaking the building you are in because visually it presents that way -- and then you will suddenly emerge into the summer sunshine and think: "Did that just REALLY happen?" as the sort finishes its work. Napoleon Sort is a soft touch on things nearly ordered, and so the contrast in its presentation is sharp at that point.
Napoleon Sort is another one I can leave on in the background, because I love the sound of a moderately vigorous storm. I don't do that with Stooge Sort for long periods of time because it worries me ... which is another hint ... sorting algorithms can mess with you because of what they do with sight and sound, just like Shepard's Tones...
Now, finally, we get to a sort that is efficient enough to be used -- with the family of bitonic sorts, you can actually HEAR that something orderly is happening in a particular data set. The wrong order is being addressed systematically, carefully disassembled, reassembled, and put up the right way -- you can hear it as well as see it, and this is thus one of the very few sorts that, played slowly enough, gives you the idea of a orderly progression.
But here is the thing: that's a slowed-down clip of the following video, and this is where things get trippy.
One cannot appreciate the musicality of Iterative Bitonic Sort at high speed (at .25 speed you can hear it again), but what you will see is a random data set being organized into recognizable shapes ... triangles ... stalagmites, stalactites ... at different scales as if you are zooming in on them at times ... and then cliffs ... then if you keep watching you will see buildings with chimneys and steeples emerging ... and then on data sets that are curved, you will see architecture from the Arab/North African/Southwest Asian world start to come out at you ... the line between how data is organized in a visual way will begin to blur that line with how nature and humans in it organize raw materials into structures. Listen to it at slow speed and the sense of how we organize rhythms from less complex to more complex and back also comes out.
What is going on here is the same kind of iterative process that can turn a simple curling motion into an alien hunk in Apophysis 2.09, my favorite digital art tool:
"The Hunk," fractal art by the author, Deeann D. Mathews
Bitonic Sorts, like all sorts, know where they are going -- an organized data set with parameters preset. Iterative Bitonic Sort is like a multi-faceted fractal artist, iterating its organizing actions until that goal is reached, just like Apophysis 2.09 took a jagged curl, scaled it, wrapped it in and around itself, and "stopped" when the data set was in the order necessary to make the shape I wanted. It is "the hunk" of sorting algorithms ... brains, patience, and brawn, and also, quite handsome to look at in a trippy way.
But for speed, power, and broad spread of musicality, Least Significant Radix Sort takes the cake. LSD Radix Sort looks at the base of the number you give it to work with (here base-10, the same base we tend to count in), break it down into that many iterations based on the least significant digit, then do it again and again until it has everything in order -- the last steps are almost identical to each other no matter what the starting pile looks like ... the second-to-last pass might sound eerily familiar, though, before resolving into the D Mixolydian scale common to this program ... but let's not go there just yet... instead, enjoy the organ-toned variations on the LSD Radix theme that this sort gives us a show of ...
Now, if someone has a LOT of computing power to spare, LSD Radix can count higher than base-10, and bring the whole band with drums ... listen to all these mini-jam sessions leading up to when LSD Radix finally gives one note out and "tunes" the whole stack ...
... and again, late in that video, something eerily familiar is heard ... LSD Radix is not only programmed to count fast and high and be stupidly quick, but it breaks the wall into a previous weird and highly warned music post I had here ... listen to this 31-second sort and listen to the final passes...
Yep. Those are ascending Shepard's Tones, and the very last sound a perfect chromatic scale. LSD Radix Sort has that combo programmed in for its final passes, and if you listen to any LSD Radix Sort carefully, even in the in-place one I put here first, you will hear a variation of an ascending Shepard's tone in the final pass or two. So: every warning that goes with Shepard's Tones also applies to LSD Radix Sort, and a few other sorts have similar final passing tones!
But here I hear the voice of the Ghost of Musical Greatness Past singing through the portal that line from the entrance of the voice in Beethoven's Ninth Symphony, admonishing us to turn our attention from all the things that have come before, to sounds more full of joy. Now we can't quite get there from here, any more than a basso profundo ought to be singing that part from Beethoven ("and although I can't get vocal strain up here, Frau Mathews, you are still going to hear about that from me later because you keep putting my bass-baritone colleagues out of work!") -- because unfortunately, one can't get emotional depth from a sorting algorithm. But, every now and again, you do find one programmed by someone on a lighter, airier path in life and sound...
Wake up late on a summer morning, hearing tropical birdsong (because of the colors here) turn into chromatic scales -- that is what this rendering of many different types of algorithms reminds me of ... and then at about minute 9, LSD Radix is in the house and brings a perfect chromatic scale which is the base of the Shepard's Tone ... and again, as all the birds have a sporting race at the end LSD Radix powers through in first place ... but then it sounds like sirens from the city come through ... and from there you may as well be in the heart of the city on a weekday morning ... until the last scale sounds, and suddenly order has emerged from chaos ... but it is quite the wonderful and colorful journey to get there!
But this is the appeal, for me and many others ... the promise that even in what seems almost impossible disorder in the world, there is a master plan running somewhere, and at some point, it will all come clear and right. Many people's personal journeys in life have periods of seeming hopelessly out of order ... the lives of families and communities and nations do as well ... and oftentimes, there isn't a happy ending. But with a sorting algorithm, things that are black and white will usually leave no ambiguous shades of gray, and all the colors will be respected and allowed to find the place where they can shine in their spectrum. If Bogo Sort forms an exception to the rule, it is this: even on the sometimes chaotic journey to getting things right in the universe, there are moments of beauty along the way if we look and listen for them.
"Lullaby in Birdland" sorting algorithms ain't ... but I love them for what they are, in a disordered world, singing out hope in their own unique way!