Batcher's Bitonic Sort

Visualization and "audibilization" of "Batcher's Bitonic Sorting Network" algorithm.
Sorts a random shuffle of the integers [1,128] and [1,1260] using Bitonic Sort, which is an parallel sorting network, where each left-right sweep could be done fully in parallel - en.wikipedia.or...
More information on the "Sound of Sorting" at panthema.net/20...

[@samnub7912]

From cathedral spires, to forest treelines, to inverted mountains. Man, this is a really artistic one!

[@nolanaubuchon6283]

Merge sort's dyslexic brother

[@want-diversecontent3887]

Nolan Aubuchon 's kinda fast cousin

[@ayamirisukahyejunghyuneuneun]

Orion D. Hunter theres delay ok

[@mateuszodrzywoek8658]

it makes some pretty fire beats in reverse shuffle

[@smaybius]

From my understanding it's a type of sorting network. It's actually a practical sort because it's made to be run on multi-threaded processors like GPUs. But because this video is showing it on a single thread, we only get to see it as its ridiculous

[@maurolionelmipianoyyo11]

64*64 likes

[@Distress.]

this algorithm is upsetting to watch.

[@IamBHM]

First it smooths things out, then it makes them jagged again. Then it smooths it back out. Then it makes it jagged again! Smooth! Jagged! Smooth! Jagged! Smooooooooooooooooooooth.

[@Srynan]

All I am thinking while watching this is: "Go home algorithm, you're drunk."

[@avivfrai4858]

It’s trying its fucking best, okay?

[@weaponizedpizza8825]

This algorithm feels like an expert purposefully giving out inefficient yet eventually working solutions just to mess with people.

[@ayior]

@@weaponizedpizza8825 which makes me wonder, what would be the least efficient goal-oriented algorithm? Not counting the one that is random.

[@TheLazySummers]

2:10-2:17 has a pretty decent beat going on lol

[@Mix.D]

It sounds like "Knife Party - Resistance"

[@whatisthis2809]

@@Mix.D i remember that song from open hexagon's ideal definition of face knocker level pack

[@Void-0194]

Kanye West Type Stuff

[@thermitty_qxr5276]

Chaos probally

[@d0gbackwards784]

1:52 is that pacman? :d

[@nenabautista5070]

yah right?

[@prestonhall5171]

Yes

[@MattPryze]

Is this actually efficient?

[@Melthornal]

Yes, it is very fast. You see how there are multiple red bars? Each bar is a separate processing thread. This sort is designed to be run multithreaded, and can run efficiently with a vast number of threads. As a result, it can sort faster and faster the more threads you have. This sort of algorithm is great for cloud computing, where you have access to vast CPU power, which is what I believe it was developed for in the first place. It also works really well with CUDA where it can run crazy fast sorts using the huge number of CUDA cores in modern nvidia GPUs. Running this sort of algorithm on a card with 1200+ cuda cores gives you great performance.

[@petter9078]

THat is interesting. Could you bother to elaborate what relation the GPU has with this algorithm? What is thread, is 1 thread using 1 core? What would this algorithm in the GPU sort? What data? :)

[@0xCAFEF00D]

Basically the performance gain from this algorithm is from the fact that every two values in the set form a pair for each iteration and can be operated on individually. There's no dependency chain between the compares as there would be in most other (non parallel) sorts. Since its so extremely parallelisable it's very fit for GPUs that have what's effectively many many cores. This visualisation is using 4 threads (4 simultaneous executions per cycle). If we moved this to the GPU where we have many many more cores effectively and we visualised that it would effectively show a 'page' (an entire movement of the red lines from left to right) per step. Which would be very fast. At this (relatively slow) visualisation speed we'd easily be done in under a second.

[@petter9078]

Interesting. Why haven't I heard about this in class? Is GPU programming hard? Or a new thing? How do I learn this?

[@Melthornal]

Just look up CUDA and the CUDA toolkit.

[@arthurk7270]

Is this what music is like in programmer's heaven?

[@MockingjayWhistle]

+Arthur K I sure hope not

[@ayamirisukahyejunghyuneuneun]

Andrea Costas it is

[@derpboi3155]

Yes, but NOT THIS. Search up Radix sort, Base 10.

[@ATIHpss64HM]

@@derpboi3155 yeeeees

[@drrenwtfrick]

@@derpboi3155 ah yes, i like iksiekaisksisksiso- BAUAHAUABAISNSHKSNSISMSHALSNEIWMBFOSMXHALSBEUWOBDIEMDUWKDBWINFUEND BUAAAUAUAUUAMRBWJAOUAKWVAUWKDBWIMSBSUWKANHDOEMSBSHEOUWJAMSJA DAAÀAAAAAÃAAAÆÄ **AAAAAAAAAAAAAAAAAAAAAA**

[@DeltaEpsilon7787]

This algorithm is quite... playful.

[@kilroy987]

Now I know where the sound effects for Pacman came from.

[@Estlib]

"slide whistle sort"

[@Ambipie]

weh weeeeeeeeyoooo Sort

[@MultiWiff]

Probably one of the most complicated parallel sort to understand properly. If you just read the code, it will not make any sense without reading the paper on this sort.

[@ashkat64]

Can someone PLEASE explain me why the bitonic sort is doing such weird shit, sorting it, then throwing it back in disorder, then sorting it again, then throwing it back in disorder again, then sorting it AGAIN??!?

[@DoubleBob]

+Evan Verburg The algorithm is designed for parallel computation (many threads) , but the video shows it linearly (one thread), which makes it appear pointless.

[@bbjygm]

So essentially wherever there is a very distinct break in the slopes it's creating, that's supposed to be one thread solving that particular portion? And then the number of threads being computed reduces as the algorithm goes on until it's all combined in one thread/array?

[@0xCAFEF00D]

The reason it looks weird is because it's indented to use multiple threads all the way through and the sorting is more effective due to that. Naively you'd think that interrupting the sort at some point where it looks 'neat' and just merging the values would be effective. But that'd introduce a dependency chain. A way to put it for people who don't have any understanding of multithreading is that this algorithm could have the comparisons be made in any order as long as you've made every comparison for each iteration this visualisation does from left to right. That has major advantages.

[@ashkat64]

oh right, that makes sense yea, thanks for clearing it up!

[@groszak1]

A proper parallel sorting visualization is available here: scratch.mit.edu/projects/193849846/

[@cortster12]

This seems like the least efficient way to sort things, but it's the coolest.

[@Glockodile]

+cortster12 iTS INCREDIBLY FAST sorry caps lock when you have like a thousand varibles

[@groszak1]

It's designed for parallel processors, doing multiple things at once.

[@tusharsingh6003]

Try bogobogo sort.

[@raffimolero64]

bogobogosort on a million integers. it might finish instantly in 1 step per 0 ms

[@want-diversecontent3887]

Bose-Einstein Paranoid merge sort.

[@mychaelmay6321]

2:00 When a small annoying dog starts barking

[@EriqireM]

at 2:00 the sequence exactly maches the pattern ABBABAABBAABABBA A->AB B->BA

[@groszak1]

It's the thue morse sequence, generated by inverting previous sequence and placing it after it. A AB ABBA ABBABAAB ABBABAABBAABABBA

[@EriqireM]

groszak1 both definitions yeild the same sequence.

[@groszak1]

Yes but I used the commonly accepted and nicer to me one.

[@tearlach47]

Ah, the Thue-Morse sequence.

[@groszak1]

bitonic sort merges AB to B and BA to A so you got this the wrong way

[@dannyundos8927]

But parallel comparators are supposed to work at once... In this video they don't, making the time complexity O(n(log n)²).I want they do, which will make the time complexity O((log n)²) in parallel times, which outstands every other algorithms. (And the same goes for Batcher odd-even mergesort.)

[@groszak1]

But then merge sort can be O(log n)

[@0xCAFEF00D]

Yes mergesort performs favorably in single threaded time. But he's talking about parallel time.

[@groszak1]

There is a merge sort modification that gives log(n) time for parallel machines.

[@groszak1]

A proper parallel sorting visualization is available here: scratch.mit.edu/projects/193849846/

[@groszak1]

imagine how much sound would be playing at once when thsi visualization is parallelized

[@Dubfiance]

OwO sort

[@lil4isab3l]

to be honest, I don't know what any of this is, but I love it.

[@thePrzemko17]

I stuck in a loop in YT. All other videos are about sorting algorithms.

[@Matheus-ki9zo]

1:19 Giygas is fatally wounded

[@sunlessheaven]

We're proud to announce, Crazybus 2.

[@The-pf4zy]

This sort is so weird... I love it!

[@SpitfireMkIIFan]

1:56 Pacman is coming by!

[@nickfarmer2452]

Kinda reminds me of 90º image rotation by swapping quarters.

[@ratlinggull2223]

Is this "Dubstep Sort"?

[@irgendwerausbayern1999]

Fat Autist XD This is actually the perfect word for this sorting algorithm.

[@shadowgirl5447]

Prop Feds no.

[@normalkettle]

Better than Skrillex.

[@PG-20]

Oof, shots fired

[@ramiel555]

ok........so, this one might be my favorite visually :D

[@felynecomrade]

I heard a tonne of Pokémon cries...

[@irksome.69]

ayo the pizza here

[@EdwardNavu]

It somehow sounds like Pac-man to me.

[@YllidTheLoonyDog]

2:45 Egyptian pyramids: Australia edition

[@PorkBoy69]

its a parallel algorithm but was visualized sequentially

[@AnonEMoose-mr8jm]

By far the strangest sorting algorithm I've ever seen.

[@ricardoescareno8135]

2:40 did anyone call an ambulance?

[@derpboi3155]

Dead, are the parent sorting algorithms, but their children live on... Bubble sort, the stubborn middle child who does it the simplest, and most inefficient way. Selection sort, the ‘perfect’ child, who is also very efficient. Insertion sort, the quiet, simple, and efficient 2nd youngest child. Batcher’s Bitonic Sort, bubble sort’s twin brother, who’s even worse. Radix Sort, base 10, the Flamboyant child, who attracts crowds with his beauty, but hides his inefficiency. Bogo sort, the youngest child, who knows no better than to shuffle until he gets it right. Gravity sort, the master of Time-Lapse video. Counting sort, the second oldest, who is known for his simplicity and efficiency. Pigeonhole sort, the most efficient child in the family, the most educated, the most successful, and also the most forgotten by his family.

[@xGOKOPx]

Bitonic sort isn't "even worse" than bubble sort. It's specifically designed to allow parallel execution, which allows it to run very fast, especially on GPUs where there are thousands of threads available.

[@SgtAbramovich]

on x2 it sounds like an old videogame

[@animatorbean3882]

bachs been real quiet since this dropped

[@FrankHarwald]

tbf, bitonic sorts are most of the time used in hardware comprising of parallel sorting networks, not iteratively like this video suggests.

[@xhourglazzezx]

better than most songs today

[@Carlos-ux7gv]

Looks like Merge Sort had a son with her brother, the Odd-Even Sort. P.S.: The same guy actually made a Batcher's Merge Odd-even Sort :-)

[@JennyTheNerdBat]

0:34 it started making tetris tgm noises

[@TalbotNC]

PacMan & Ghosts really going at it

[@NoriMori1992]

It was like it was trying to draw mountain ranges the whole time.

[@freedustin]

Sounds like Q*bert and Pacman gettin' it on.

[@ATIHpss64HM]

This is interactive bitonic sort

[@zerstortewahrheit607]

That's incredible!

[@HitLuca94]

huh, greetings

[@elliotbidwell9684]

This is how they make jazz

[@Ambipie]

He look strange but hes thinking in 2 dimensions. In fact... How many sorts is in this blender?

[@beckybecky125]

2:10 is a bop

[@XElhirrimX]

When you like bubble sort, and comb sort, and merge sort

[@insertcreativenamehere5473]

Kracc Bacc videos in a nutshell

[@Anikin3-]

I was listening to childish Gambino and then I saw this video so I clicked on it and this sounds better

[@ashtonlewis4814]

It's a shell sort, but based on bitonic sort instead. Right?

[@groszak1]

it's bitonic sort, done in a different order

[@ravja44]

This sounds like singing class... 123454321!

[@littlecloud1977]

i like this song

[@tezer2d]

_Bitonic sort_ hurt itself in its confusion!

[@DuringDark]

everyone who doesn't like this sort or the way it looks/sounds must fight me to the death

[@DolanTheProtogen]

I think batcher was drunk making this

[@raffimolero64]

does anyone else notice the thue-morse sequence in the direction of the piles? rise-drop-drop-rise-drop-rise-rise-drop-drop-rise-rise-drop-rise-drop-drop-rise 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

[@Lady_VythikaPlays]

Sounds like Pac-Man having a stroke! Fascinating to watch though!

[@Pgpxd]

Ah, yes my favourite.

[@soulendex36]

Peak content

[@SaeedAcronia]

Jesus! I might as well start sorting by hand.

[@NintendoSushi]

this looks like *the* most inefficient sorting algorithm ever...

[@randomcatdude]

It's designed for multiple threads, so if you could run this with a hundred different threads, it would finish very quickly.

[@NoshuHyena]

Evil mountains!

[@maxwellstrange4572]

this is wild

[@EmberAlberson]

1:56 PAC MAN

[@steveday72]

It starts to sound like it's playing a game of Pac-Man around the 2min mark!

[@wondermittens1844]

Bloop bloop bloop

[@cinderg1ock]

bleep bloop bloop bleep

[@shadowgirl5447]

0:19 - 0:30 what Code: Pandorum Sounds like to my parents.

[@duckypolice]

WHERE IS THE DOWNLOAD THO??

[@had2chan]

DUBSTEP

[@masicbemester]

Isn't it supposed to be Beanduct Creampatch instead?

[@masicbemester]

How to delete a comment?

[@MandrakeGuy]

So how does this work

[@Rodentsnipe]

FeelsGoodMan Clap

[@groszak1]

A proper parallel sorting visualization is available here: scratch.mit.edu/projects/193849846/

[@ducktape5970]

R2D2 high on drugs

[@ap155mm6]

how did i g here after watching black sabbath?

[@Fera-gr5mm]

Sound of the police

[@applejuice2898]

Me when spicy chip

[@austbob7161]

This just sounds like slide whistles lol

[@zanzi_]

Looks like its drawing

[@lumirbaca1831]

It's a Burj khalifa building program!

[@jjjthe_dark7260]

1:19

[@koykong3122]

Wooaoowooaoowooaoow

[@WellIAmTheOne90]

I should probably do my homework

[@larshanselmann6514]

Bogo 4 president

[@webx135]

This algorithm seems outrageously inefficient but Pac-Man.

[@AnimMouse]

Not when you run this in GPU.

[@user-pc4pv9sw1b]

that sort is too faster XD

[@daonion421]

horror game effect

[@aryamaangoswamy179]

longer than (video of) bogosort xD

[@electricengine8407]

My internet has broke :(

[@akashi2468]

PACMAN

[@jakewarren2369]

doesnt seem very efficient at ALL

[@Wren6991]

You're wrong, and if you'd bothered to read the video description (which is all of 3 lines) you would know why.

[@jakewarren2369]

i did and i mean low LONG it takes compared to other algorythms that take far less time

[@Wren6991]

Okay I'll even paste the relevant part of the description for you "which is an parallel sorting network, where each left-right sweep could be done fully in parallel" It's shown here in a serial manner, which is why it appears to take longer. In reality, because the algorithm avoids dependency chains, an entire pass can be calculated in a single step on a sufficiently wide machine, which makes it much faster than any serial sort (e.g. quicksort) If you click on the link IN THE DESCRIPTION then you can see it has a delay of O(log^2(n)) if your hardware is able to take it fully parallel. If you pipline it, you can get a fully sorted array out every single clock cycle -- that's O(1) sort. Compare to O(n log(n)) for serial sorting algorithms.

[@metrabyte1282]

This sounds like PAC man having a seizure

[@HHH-yu2xp]

gwet rid of them ad!

[@ritujha7009]

Wtf😒

[@SlashCrash_Studios]

Botch Once Get Old sort (BOGO) sucks

[@randomgladospotatogaming4724]

Why does this algorithm exist? It's inefficient and a waste of time

[@groszak1]

It's supposed to be used on parallel computers, which can do infinite operations at once. If so, this is O((log n)²) which is efficient. This cannot be done with most algorithms because each operation depends on the previous one. A proper parallel sorting visualization is available here: scratch.mit.edu/projects/193849846/