50+ Sorts, Visualized - Reversed Inputs

[@Musicombo]

Join our community Discord! discord.com/invite/2xGkKC2

[@DerpyNub]

Rip no likes :(

[@bryceg1020]

Every other sort-uses givin values Gravity sort-yall mind if I just *c h a n g e t h e v a l u e s*

[@bendaonfire0078]

What if i set them all to the same value BOOM Sort skill 100

[@tiporial]

pizza mozzarella pizza mozzarella rella rella rella rella

[@soulsilversnorlax1336]

@@tiporial this comment could be a big hit in Europe

[@LabyrinthFunkinDev]

Everyone else: “Keep with the values.” Gravity Sort: “My name may have Gravity in it, but I defy *_a n y t h i n g I w a n t .”_*

[@Apfelbaum454]

You: Gnome Sort The Guy she tells you not to worry about: Optimized Gnome Sort

[@diceLibrarian]

You've just been G'Nome Sorted

[@thisrecordingsessiontm3633]

Her father: Odd-Even Sort

[@Dinosaurs_with_laser_guns]

Lol 😹

[@MrCubFan415]

(insert keemstar joke here)

[@AtariWow]

Max Heap Sort

[@roshambo4137]

"Yo pass me the aux cord" "You better not play trash" *plays the In-Place Radix LSD Base 16 Sorting of reversed inputs with 2,048 numbers*

[@alluseri]

timecode ples

[@alluseri]

Timecode: 11:10

[@GoldenGamerFox7272fromYT]

timestamp*

[@lilmarionscorner]

Alluseri timestamp: 11:10

[@souplover6845]

My jam

[@kunyoruyo]

18:20 "ok let me fix that... wait... no... what's going on??"

[@estergallardo3594]

This comment is not cool 😻💪👎🤙👎😽💪👎😻👎🙀👎😼🤞🎃👺👹

[@michaleatsonionsforbreakfast]

Ixpantenco it's pancake sort

[@hollyleaf3941]

@@estergallardo3594 And you're cool I suppose?

[@Pallid3]

It's just robot

[@dragonsdream4236]

@@spedur3361 found the thirteen year old

[@superscatboy]

Programmers in theory: look at all these options we have for sorting in different situations Programmers in practice: std::sort

[@lychy645]

superscatboy truu

[@benjaminschaaf]

Pigeonhole sort requires a limited range of integers (or equivalent). Using pigeonhole to sort a list containing just the numbers 1 and 1 trillion (1000000000000) requires 8TB of storage for example. It's great when you have a large set of integers in a small range, but that's almost never the case in practice.

[@bathbombman]

quicksort when

[@somenamelastnaammee52]

_Arrays.sort();_

[@firstnameiskowitz8493]

16:27 when you have five minutes left to finish all the questions in your exam

[@CJBox9]

lmao that actually made me nose laugh

[@victorfunnyman]

nose expiration ye lmao, it got quick so weirdly

[@JetFalcon710]

"Alright screw this. YEET" -Weave Merge Sort 2019

[@nejitentenlee21]

I finally understand how gravity sort works! It doesn’t sort by moving, it changes the value of the item in each place until it’s the right value for that place

[@Musicombo]

Yup! Uses a lot of scratch space in memory to do all that subtracting/adding, as well.

[@jacobw1780]

What is min heap sort then?!

[@devinandcarrietotaldrama505]

@@Musicombo how about counting sort?

[@RubyPiec]

Can you give an example using numbers?

[@uzairm3816]

@@mrninjagon270 @chacha charlie well technically you can consider non descrete values to be discrete, but there is only 1 of each value. It would be really inefficient, not impissible for the counting sort

[@caseyashworth8016]

Smooth sort: is called smooth sort Also smooth sort: 5:24

[@yonka-cola8792]

Spiky

[@louispipercarson9630]

pointy sort

[@givrally]

I was just about to say that ! It's literally the least smooth of all, maybe excluding heap sort variants.

[@brayden205]

Casey Ashworth I think it’s called smooth sort due to how quick and clean the sort itself is

[@raybeetle]

Ru²Kanga clean?

[@wow-uf9ke]

pancake sort be like bruh

[@dannadx3840]

Man, not all sorting algorithms are designed to work with purely this type of data. Probably it was developed for something very specific

[@dannadx3840]

Yeah, it certainly is. I got time and checked. The only available operation is element flipping, so it just wasn't designed to work in this data type

[@jr01theweeb]

18:20 The sort took 3 minutes

[@-1f]

my mans be like bruh

[@ilikeceral3]

dannad x what the heck is pancake sort for then?

[@ThomasBomb45]

2:12 looks like a rotating 3D image. Nice

[@draganahajdin404]

It does!

[@err0rcube115]

Omg it does lol

[@victorfunnyman]

true tho

[@JetFalcon710]

Yeah, it's like watching someone rotating an empty box

[@sawyermerkle8835]

4:43 And here, you see a sorting algorithm sorting a reversed input to another reversed input...

[@EJayy13]

Min heap sort is just wrong.

[@edwardclark6731]

4:49 SIKE

[@EJayy13]

@@edwardclark6731 no

[@Tekkwin]

is this how they made earthbound sounds

[@Musicombo]

Hahaha :P

[@jacobw1780]

No.

[@Pedro270707]

@@jacobw1780 r/woooosh

[@jacobw1780]

@@Pedro270707 O H N O

[@trashmann1081]

pk algorithm

[@demonschnauzer1555]

17:21 Introsort: Well, I just completed my task, better celebrate!

[@mamf6175]

Set Playback Speed to 2 to improve the algorithms

[@dirtydan9785]

big brain moment

[@EJayy13]

Or 720p60

[@maurolionelmisjuegosyo940]

No

[@LunarLambda]

poor pancake sort

[@jacobw1780]

18:22

[@amethystt727]

It tried, but it just wasn't enough

[@uklu]

Still faster than bubble sort

[@panze-r]

It's a joke sort so its born to be trash unfortunately

[@StormTheSquid]

It's just showing off.

[@glitchy9613]

26:34 So we've made the pattern just the reversed version of what the order is supposed to be, so its easier for you to sort them. Less Bogo Sort: Ok...

[@JiMMy-xd8nu]

omg yes

[@ojd9145]

Yeah

[@Coolmanerik_Z]

relatable

[@dr.jacksonbright5723]

Imagine using silly sort on a comically small set, thinking “maybe it’s silly’s time to shine,” only for your computer to freeze for seventeen and a half seconds before presenting a sorted set

[@californium-2526]

A set of 256: 17,5s A set of 2048: 1m41,6s or something

[@Musicombo]

It doesn't work like that; it's not linear complexity. 2,048 items would probably take over a day.

[@californium-2526]

@@Musicombo Ah, the beauty of O(n^(log n)) (didn't know that it was that bad while I was making that comment)

[@BigFatWedge]

Silly Sort took 572 MILLION COMPARISONS to sort 256 items!! XD

[@pencrows]

Patience Sort: get your popcorn and take a seat, we're gonna be here a while Also Patience Sort: 2 seconds

[@edwardclark6731]

thats terribly inefficient if it was real time

[@colouur4778]

9:57 wait that’s illegal

[@EXA1024_]

ikr

[@maxhaibara8828]

Bogo Sort can be the fastest sorting algorithm, with the chance of happening of 1/n!

[@DragoStar]

I may be late but is that 1 over n factorial or is it an excited 1 over n ?

[@MineSomeCraftPoo]

@@DragoStar this is probably a joke, but hey, anyway it's n! since thats the total number of ways to order n elements

[@almogz9486]

@@DragoStar 1 over n factorial

[@asheep7797]

@@DragoStar 1 over nfactorial

[@LindenF]

5:25 I’m sure that is not smooth it looks sharp

[@screamsinrussian5773]

no

[@brayden205]

I’m pretty sure it’s called that due to the sporting not being sloppy or confusing as others

[@edwardclark6731]

smooth heaps: *am i a joke to you?*

[@edwardclark6731]

Future me: *Yes. Yes you are.*

[@icebearpl188]

When bad sort gets to be one of the fastests

[@jacobw1780]

Good sort

[@katalysator3431]

well it doesnt use as much numbers so...

[@Digephil]

2:50 my guinea pigs when I'm cutting bell peppers.

[@Zyn_Shi]

I’m glad someone had the same idea!

[@ojd9145]

yeah

[@fachriem]

i really love 10:36 so much! easy algorithm and yet best performance~

[@californium-2526]

Ah yes. 573 microseconds ERT, just behind of TimSort (391 microseconds ERT, 16:32) It's a storage and memory (?) hog though.

[@jeremyaster7470]

pigeonhole sort just built different

[@entredus7910]

elements 1 and a really, really big number

[@Lonely_Wiz]

21:34 flight of thr bumblebee

[@chimaudeh5159]

Love how the smooth sort (5:24)is in no way smooth

[@bingobeego]

LMAO

[@JetFalcon710]

Smooth sort actually roughened up the surface of the triangle

[@diamboy]

Base 16 looks like it’s trying to say something

[@pittagiiya]

Sounds like it's trying to say something; not sure whether that's what you meant to say or just what I think

[@jonasferraz]

11:11

[@MrtinVarela]

Batcher's bitonic: *"yes, but actually... no"*

[@mateuszodrzywoek8658]

it does make some pretty fire beats if i say so myself

[@NXTangl]

That's just what happens when you're literally the opposite of adaptive!

[@jyosongurung5583]

That’s at 12:58

[@jyosongurung5583]

Also what the $%#&?????

[@Fireball7428]

And then there's Pancake sort at 18:20.

[@aether-music]

16:24 "Nope, I'm done"

[@ZA-mb5di]

17:21 sounded like All Star for a second

[@fridaykitty]

nice 69th like

[@pannesterpants3008]

Omg ur right

[@galimantis]

10:29 _What._

[@twoarrow9134]

“yeet”

[@thatcrystalpie]

The algorithms have learned to count

[@lillie3029]

Galimantis 10:37 *

[@wenirlicker6808]

Count Count Sort

[@JNSStudios]

H O W

[@sillybeanthing]

I like it when the red line is stuck focusing on one point like it's working super diligently to sort the things in the area, then it goes to another place and starts again

[@ninja3212]

TimSort be like: "Y'all mind if I just flip the array?"

[@californium-2526]

Est. Real Time: 391 microseconds.

[@Hjerpower]

I like how min heap sort went through the whole heapification process to only end up back where it started

[@BigFatWedge]

See, YOU can see all the items at once , but the algorithm cant. It can only compare two items at a time. To us, it just looked like Min Heap Sort turned a reverse array back into a reversed array. But to Min Heap Sort, it turned an array of didn't know was reversed, to an array it DID know was reversed.

[@deffinatalee7699]

12:58 Batcher needs to make up his mind

[@FusionArmorX]

12:27 The sound of 100, 500, and then 1000 point enemies being destroyed.

[@TheEgglet]

2:17 it looks like a hole in a box lol

[@Obviary]

3:02 if you listen closely it almost sounds like megalovania

[@attack54]

Obviary god damnit take my like

[@amogus7]

42th

[@quillenkai6714]

I thinks it's absolutely amazing that bogo sort with 8 inputs took nearly 10x as long (estimated) as quicksort with 2048 inputs

[@Hasde_dfs]

And that’s without even talking about pigeonhole sort

[@kingsley.]

@@Hasde_dfs tim sort

[@rexperverziff]

@@Hasde_dfstime stamp?

[@locrianphantom3547]

Wait til you see BOGOBOGO sort…

[@bogdan_ostaficiuc]

​@@locrianphantom3547with 10 inputs!!!!

[@Jack-lp3gc]

so is no one gonna point out that min heap sort did a bunch of stuff to the inputs only to get right back to where it started and then flip it around

[@ATtiny13a-PU]

11:10 - is drop from dubsteb

[@taureon_]

which

[@screamsinrussian5773]

dubsteb

[@EdKolis]

I like the ones that don't even maintain the integrity of the original data but somehow put it all back at the end, like the gravity sort

[@mcbattery856]

Where's that comment with the list of sorts?

[@busher6004]

Gone Reduced to atoms

[@marcosgreg9983]

Seems not sorted yet

[@MishaG4mer]

Counting sort: I am speed Patience sort: You are quick, But im faster

[@MishaG4mer]

Time Sort: Hold my beer

[@MishaG4mer]

TimSort: Try me bitches

[@finniko1995]

Pigeonhole Sort: Boom, done! What now?

[@MishaG4mer]

Pancake sort: YOU DARE OPPOSE ME MORTAL Hold on gotta scan the algorithm 69420 times before confirming its sorted

[@ConsarnitTokkori]

pancake sort: merry christmas 2016!

[@buurk]

11:11

[@Memerath]

the time, the sort, the mathematical perfection of it all

[@takedLLC]

Is no one going to mention that at one point gravity sort had all of the numbers the same?

[@ironoat]

You should look up gravity sort. It's a really cool concept. You could build a physical system using it to sort in linear time. It is also called bead sort

[@Choinkus]

It's pretty cool but unfortunately it's not very efficient

[@dezcubing5844]

I saw from another comment that it changes all the values until its the right value for the place

[@cephalosjr.1835]

Choinkus Gravity sort is only good on specialized hardware. Of course, if you implement it on hardware, it’s very fast.

[@takedLLC]

@@ironoat I know

[@bigloudnoise]

I'm surprised Pancake Sort didn't see the obvious solution of just flipping the entire stack once to get it in the correct order. I presume there's a limitation to the algorithm (which I am unfamiliar with) that forces it to start inside the stack, thus preventing it from just flipping the whole thing in one shot.

[@BigFatWedge]

Pancake Sort searches for the largest item in the remaining list, and then reverses the part of the list ranging from the first item in the list to the largest item. For example, if the largest item is the 50th item, reverse the order of the first 50 items. This puts the largest item(in the remaining list) at the front of the remaining list. Then you reverse the ENTIRE remaining list, putting the largest item in the last position in the remaining list. Then redesignate the last(largest) item as part of the sorted list. Then do it again on the remaining list, until it reaches a length of 1 item. It's basically Selection Sort, but made much worse for no reason. So, in this case, on the first iteration, it finds the largest item(already the first, as the list is in descending order), then reverses the list from the first item to the largest item(since this is a list of 1 item, nothing happens), then reverses the entire list, which sorts it. But the algorithm doesn't check if the list is sorted, it just searches for the largest item in the remaining list. Because it reversed the entire array, putting it in ascending order, the largest element in the remaining list is at the end, making the algorithm reverse the entire list to put the largest item at the beginning, then reverse it AGAIN to put it at the end and thus sort it. But it isn't checking, every time it reverses the array, if it's sorted. In short: although it sorts the list in "one shot," it doesn't KNOW if did that, cause it didn't check. Hope that answers your question.

[@SKyrim190]

Some of those look to me like (1) read the list (2) print the sorted list is the whole algorithm. I can not even begin to guess what is going on. Also, silly sort looks like a merge sort that got neurotic and is afraid the list might change when he is not looking

[@ThomasBomb45]

They use auxiliary data structures. The visualization really should show them

[@FunctionGermany]

Batchers Bitonic Sound be like: "now i know this might look like the exact same thing but just hold on for a bit"

[@niku4154]

Nobody: Old PCs when you put in a CD: 18:13

[@wladfan]

Whoops! You have to put the CD in your computer

[@Guinea.Pig-Gaming]

odd-even sort looks like a 3d structure changing shape.

[@DogeisCut]

It does tho

[@sameendusk2623]

16:32 timsort's not having any of this reverse bullshit

[@Caseofgames]

9:57 Perfectly balanced, as all things should be.

[@thatonecountryballanimator]

9:58

[@Caseofgames]

@@thatonecountryballanimator It's already unbalanced at 9:58.

[@thatonecountryballanimator]

Whoops, sorry.

[@ilikeceral3]

Why am I watching sorting videos when I don’t even know math

[@thatcrystalpie]

Pigeonhole sort is like "I SEE THROUGH THE LIES OF THE *reversed inputs"*

[@notquitebleu]

Everyone gangsta til odd-even sort makes the sorting 3D

[@Giyga]

I find pancake sort very funny when it starts swapping rapidly towards the end

[@MayorVideo]

7:52: the best one

[@mikaroni_and_cheez]

Merge sort is kind of how people sort things, you group similars together and then pick out the similarities to those groups and so on until 0 to 100 are lined up

[@mistycremo9301]

I wish you would do a bit of color coding for what state the sorts are actually in- say green for "known to be sorted", and maybe separate colors for each layer of heapsort's heap

[@RichConnerGMN]

nice pfp

[@IronBoy-hf2lp]

@ Pancake Sort: BRUUUUH WHAT ARE YOU DOOOOOOING

[@nathanzotov1160]

batchers bitonic be like: Ok yeah, go there, uh huh, wait stop! Go back, go back. go right there. Yeah. WAIT NO COME BACK HERE!

[@relt_]

i love how batcher's odd-even merge sort just *transitions* the values

[@AlisterCountel]

This made me curious, is there an algorithmic way to find the specific “worst case scenario” for any given sort? Between this and the already sorted inputs, it certainly seems like there are some non-random arrangements which take excessive amounts of time compared to a normal sort.

[@Musicombo]

It's probably more often that people have just come across worst cases for these sorts, but I'm not sure about an algorithm. I would be curious about that, too!

[@erikprantare696]

I'll try to prove that there doesn't exist a general algorithm for that, in a similar way that you prove that there is no general way to solve the halting problem: Assume that there is an algorithm A(s, i), that tells you whether an input i is the worst case input for a given sorting algorithm s Construct sorting algorithm S, that given A(S, i), will sort using quicksort if i is the worst case input, and otherwise use bogosort (or any other algorithm that is going to be slower than quicksort) But, this means that for I = worst case input for S, A(S, I) /must/ say that I is not the worst case. Therefore, there exists no general algorithm A that can determine if a given input is the worst case scenario for a given sort. I hope this makes sense :)

[@Musicombo]

@@erikprantare696 That does, thank you so much!!

[@slycordinator]

"Between this and the already sorted inputs, it certainly seems like there are some non-random arrangements which take excessive amounts of time compared to a normal sort." While that seems true, there are exceptions. For instance, insertionsort is faster for "nearly-sorted" and "completely sorted" lists than for ones that have random data. In fact, it's why one method used to speed up something like quicksort is to simply do nothing when partitions are fairly small, then when that whole thing completes, run insertionsort on that mostly-sorted list. edit: What I'm getting at is that the same non-random arrangements don't affect each sort the same way.

[@Fera-gr5mm]

Brute-force algorithm might go through all n! permutations and measure it manually.

[@52.yusrilihsanadinatanegar79]

Batcher's Bitonic Sort "wait, let me merge it in" "oh wait, there is a problem" "ok then, i'll reverse it back to fix that problem" "oh wait, it's the input" "let's merge it all to-" "r e v e r s e a n d m e r g e"

[@EchoFaustMusic]

I always found it strange why block sort algorithm seem to, for lack of a better word, carry numbers along while sorting.

[@Musicombo]

That's their internal buffer!

[@AntonDiaz7]

18:21 Pancake Sort: I can finish it fast but I'd prefer to torture it.

[@shoobfloof22]

Time sort: Estimated Real Tome: 8,192 ms That’s only 8.1 seconds, but it feels like eons compared to the rest of the sorts... Edit: never mind. Silly sort and slow sort killed it. Lmao.

[@theairaccumulator7144]

Yes, because time sort works by waiting in many threads at once.

[@jacobw1780]

Tournament sort?

[@lithiumwyvern_]

That's because time sort isn't a real sorting algorithm. As the air accumulator said, time sort is just a horrible abuse of the system's scheduler - it creates one thread for every element, makes them wait (value of the element × 4) milliseconds then push the element onto the end of the output array, then insertion-sorts that array.

[@MauveDash]

Slow sort

[@nick1752]

@@lithiumwyvern_ ngl that's kinda genius

[@Drachi-]

2倍速で聴くとめちゃくちゃ気持ちいいです！ I love listening to it at double speed.

[@tizianodellafazia2309]

Ahhh yes it's this time of the year.... youtube strikes again with that algoritm stuff

[@nordern1]

The algorithm wants to show off its family

[@pestermaster7617]

Batcher's bitonic sort: shakes a bit here and there, decides that it is wrong, Puts it back, and then decides that it prefers the list sorted.

[@brandonklein1]

Really shows the difference between n^2 vs nlog(n)

[@h0verman]

its cool how with starting reversed some sorts approach a fractal pattern initially

[@zapdragon5942]

Then there's Odd-Even

[@icebearpl188]

Base16 made some sort of rbg boss battle theme intro

[@kirbycreep]

@@icebearpl188 some *_sort_*

[@Remon_]

5:26 sounds like pulling off a long piece of plastic on a new surface

[@ONS0403]

Quick sort is the one true god... considering its performance and how quick it is to write

[@romajimamulo]

Except this is actually the worst case scenario

[@Fera-gr5mm]

@@romajimamulo Only if it was choosing the last/first element. In this case, the middle element is the median, so this is pretty effective.

[@romajimamulo]

@@Fera-gr5mm That is true.

[@entropic-decay]

odd-even sort: *just turns it around in 3D*

[@jamesallen74]

No matter what the sorting video is, Radix LSD Base 4 NEVER fails to impress me in terms of awesomeness and beauty. :)

[@Fireball7428]

And it also sounds great.

[@What-thaW]

5:26 Cha cha real smooth

[@timetree4124]

5:23 Selection Sorts: Smooth Sort Looks: *Rough*

[@wymarsane7305]

4:50 "I worked so hard, and got so far But in the end, it didn't even matter"

[@Scudmaster11]

7:45 patience sort be like

[@Poopooproductions1]

11:11 drops sick beat

[@SHIN2025_official]

5:11 Weak heap sort: I AM NOT WEAK

[@sumandbastitv2606]

Strong heap sort?

[@GoldenGamerFox7272fromYT]

imagine you had 8 pencils and had to do 125984 comparisons, 585800 swaps and 1171600 writes to main array to sort them from smallest to biggest. thats the bogo sort. (27:01)

[@CatFace8885]

Pancake sort constantly reversing the already sorted array over and over not knowing any better is such a moment

[@Gamesmarts194]

“Impractical sorts” lol

[@raine6813]

12:57 "maybe if i put this he- no that dosent work. maybe if i did thi- no that dosent work either. maybe if i jus- oh god now i gotta start all over..."

[@gameborge]

counting sort when pigeonhole sort walks in

[@pinguin4898]

heap sort is extremely powerful here because it's already all in a heap

[@MsZiomallo]

Pigeonhole sort (10:37): *I AM SPEED*

[@MaximG.]

11:14 - this reminds me of Metroid Prime title screen for some reason

[@littlelamp100]

22:31 windows trying to search for a file

[@aaplies8879]

I really have to appreciate min heap sort (4:38) taking all the extra time to reform the input then flip it.

[@The4stro]

stable quick sort was like trying to start an engine, and it finally starting

[@NStripleseven]

Batcher's bitonic sort undoes itself many more times than is necessary. 13:00

[@KingofJ95]

Silly Sort: Who are you? Merge Sort In Place: I'm you, but stronger.

[@LandonM_Earth]

0:33 looks like a reversed image of the original zooming out of existence

[@korriannavanheart8911]

Dreams be like: you must go up these stairs The stairs:

[@grande1900]

It's called pancake sort because it looks and sounds like a frozen pancake spinning like a coin

[@nouche]

Is it me or did Bogo Sort get quite lucky there?

[@sharpesttoolintheshed492]

Gravity sort be like: 1) have values to sort 2) look at them 3) ??? 4) profit

[@californium-2526]

A slow one though. Pigeon hole sort, counting sort and TimSort would have fit.

[@nouche]

Quick Sort is known to be pretty bad in this case, as well as when it’s already pretty much in order. On the contrary, Heap Sort(s) are known to be pretty darn good in every case.

[@BigFatWedge]

Well, a reversed array is necessarily a heap, so Heap Sorts already have half their work done for them in this case. I imagine they don't do so well if the array is sorted/is close to being sorted, because an array in ascending order is what might be dubbed an anti-heap--no part of the heap is correct. Quick Sort only struggles because usually, it's programmed to just choose the last item as the pivot, which is bad If that's the biggest/smallest item. If you code it to just pick a random item from the list as a pivot, though, it performs just as well as any other time. Also, Heap Sort is the worst O(n log n) sort on average, and Merge Sort does better in "all cases." So you're wrong .

[@bingobeego]

​​@@BigFatWedgeigeonhole? Or even timsort