Batcher's Odd-Even Mergesort

Visualization and "audibilization" of "Batcher's Odd-Even Mergesort Network" algorithm.
Sorts a random shuffle of the integers [1,128] and [1,1260] using the mergesort network, 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...

[@daniellelarrabee285]

I have discovered the sort fandom

[@honchokomodo]

+Danielle larrabee hey it's better than the furry fandom or the undertale fandom

[@daniellelarrabee285]

Honcho Komodo true

[@rikuurufu5534]

This is my Sortsona LOL

[@dolphine373]

Honcho Komodo hey! I like undertale!

[@ENCHANTMEN_]

things are heating up in the sorting algorithms fandom

[@anabanana3458]

I like how up until 1:09 you hear something similar to music, then 2 seconds of silence, then the horrid screams of tortured souls

[@normalkettle]

WHOP WHOP WHOP WHOP WHOP WHOP WHOP

[@DaVince21]

Man, I'd love for someone to try to create a MusicSort that will prioritize the sorting process to sound musical. Perhaps by sorting values according to a pentatonic scale or something.

[@AnnoyedArt1256]

slow sort is kinda that

[@hymnodyhands]

I thought of the pentatonic scale too ... the problem is the limited number of notes available to the human ear in that scale ... even with multiple instruments, that would pose a problem in big sorts...

[@MishaG4mer]

0:19 It sounds like bogo sort

[@totallynotlilly]

i have no clue what's happening but i love it

[@54e]

The first sorting handles 128 elements that correspond to the width. There are log128=7 stages and 28 passes in total (which means the red lines transition from left to right 28 times). 0:00~ stage 1 (log2 = 1 pass) 0:03~ stage 2 (log4 = 2 passes) 0:07~ stage 3 (log8 = 3 passes) 0:14~ stage 4 (log16 = 4 passes) 0:23~ stage 5 (log32 = 5 passes) 0:35~ stage 6 (log64 = 6 passes) 0:50~ stage 7 (log128 = 7 passes)

[@raffimolero64]

i think it merges blocks, and then merges smaller blocks, and goes until it's 100% merged, then merges again

[@aycc-nbh7289]

Redstoneboi I think that’s wikisort.

[@smaybius]

It's a sorting network, meaning it follows the same sequence of comparisons per input length

[@PRINTORO]

Kids in kindergarten after one of the students do something bad 2:52

[@johngeverett]

That's gotta be the WONKIEST sort algorithm ever!

[@maxonmendel5757]

This sort seems rather... thorough

[@thesammo4499]

WOWEE!! It's like a less efficient merge sort!

[@andrewliu2539]

Sammy Vermillion Actually, every red bar is a thread, so if we were to run this sort on a GPU for instance, we could have a full "page" of red bars moving across the screen and sorting.

[@jonnynik7626]

how would this be superior to the classical merge sort??

[@debtmaster]

It is very simply implemented in hardware (as much as anything can be), and can be multithreaded. It's convenient for computers.

[@RipleySawzen]

@@debtmaster I wish they'd do a multi-thread sorting video

[@jacobschmidt]

@@debtmaster is time complexity still nlogn?

[@aycc-nbh7289]

Jacob Schmidt It is (n log n)^2, although it is apparently faster than conventional MergeSort unless n is larger than the memory capacities of all computers in the universe... in 1998, i.e. it’s only a matter of time until it obsolesces.

[@myrjavi]

@@aycc-nbh7289 n (log n)^2, (n log n)^2 would be n^2 does it really matter if the comment is 2 years old ._.

[@akimbo75ty65]

my mum processing that online games cant be paused

[@Howtard]

Neat, I only worked out that the number of peaks halves each time it "merges" a set near the end

[@s.sinster]

1:12 *dad is in the store getting and it storms*

[@joblessalex]

Instead of comparing, why don't they just assign each one a number and order the numbers?

[@joblessalex]

***** So find x, move x to pos 1 x++

[@MolotowCocktail24]

joblessalex you need to sort the numbers after all.

[@TheJamesM]

+joblessalex This kind of solution only really works in the trivial case of sorting a continuous list of positive integers. Also, it's not very space efficient - you need a separate array for the sorted output, otherwise you will overwrite unsorted data every time you move something forward. You might want to look into radix sort, however. It's not quite as simple as your proposal, but it is still fairly intuitively straightforward, and it also requires zero comparison. It basically treats the values as text strings and sorts it alphabetically (there are two variants - one that starts with the most significant digit, and one that starts with the least). These require that the data keys be some sort of positional notation. I particularly like the animations for the least significant digit version.

[@WilliametcCook]

Look at Cycle Sort and the Radix sorts.

[@stevend285]

Look up "counting sort"

[@nicholasdurant2851]

no gud work hardr

[@anders8206]

"He's the next the Mozarten, just saying... " Wolfgang Amadeus "I like cabbages" Mozart ps this is a reaaaal good quote, je?

[@PoltergeistHC4L]

Amayzing, it takes somthing it has passed and moves it infront.

[@teeth.2162]

It’s like a merge sort but with 8 more steps.

[@EriqireM]

this is what, xln(x)^2 computations with 0 additional data usage, neens neat.

[@SlashCrash_Studios]

Shell-merge sort

[@daniyarkussainov9341]

very nice results

[@optivion]

Just in time for Halloween!!!

[@PaneledPear]

Just in time for Halloween!!!

[@mr_mjrmgames3176]

I code in java, could you tell me how to do like this? Thank you

[@daniellewilson8527]

What program do you use to make these?

[@AwangardaGames]

Sound Of Sorting

[@Lykrast]

Looks like I can't find this one in Sound of Sorting 0.6.5, that's weird.

[@groszak1]

it was made after Sound Of Sorting 0.6.5 was released

[@inwencja2009]

Random computation time? Disappointing.

[@raffimolero64]

no, it's a parallel sorting algorithm. it could be implemented with comparators in O(log_2(n)) time when paralleized.

[@vrintex]

Interesting, but not quicksort

[@SpamDestroyer]

Yeah but it supports gpu multithreading.

[@myrjavi]

Merge/Shell sort

[@FishKungfu]

Cool!

[@dannygaming9643]

PACMAN feeling 😅

[@LVETOT]

Wiki sort?

[@thanhparamotor]

help! i can't install this program in ubuntu, i use chmod +x ... and i run it with ./

[@manuperez9409]

1:49 🥶

[@raffimolero64]

found my favorite sort

[@minecraftermad]

terve?

[@jurekszczurek2896]

tuloa

[@minecraftermad]

:D

[@user-js3il6xf9b]

I was the 420th like

[@balls413]

Can't wait for part 30

[@EriqireM]

this is what, xln(x)^2 computations with 0 additional data usage, neens neat.

[@petter9078]

Isnt that pretty slow?

[@dorukayhanwastaken]

SPACE it's actually between insertion sort and quicksort in terms of speed