50+ Sorts, Visualized - Reversed Inputs 

Rip no likes :(

You've just been G'Nome Sorted

Her father: Odd-Even Sort

Lol 😹

(insert keemstar joke here)

Max Heap Sort

timecode ples

Timecode: 11:10

timestamp*

Alluseri timestamp: 11:10

My jam

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

pizza mozzarella pizza mozzarella rella rella rella rella

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

9:46

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

Ixpantenco it's pancake sort

@@estergallardo3594 And you're cool I suppose?

It's just robot

@@spedur3361 found the thirteen year old

superscatboy truu

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.

quicksort when

_Arrays.sort();_

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

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

18:20 The sort took 3 minutes

my mans be like bruh

dannad x what the heck is pancake sort for then?

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

What is min heap sort then?!

@@Musicombo how about counting sort?

Can you give an example using numbers?

@@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

Min heap sort is just wrong.

4:49 SIKE

@@edwardclark6731 no

big brain moment

Or 720p60

No

Spiky

pointy sort

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

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

Ru²Kanga clean?

lmao that actually made me nose laugh

nose expiration ye lmao, it got quick so weirdly

18:22

It tried, but it just wasn't enough

Still faster than bubble sort

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

It's just showing off.

Hahaha :P

No.

@@jacobw1780 r/woooosh

@@Pedro270707 O H N O

pk algorithm

It does!

Omg it does lol

true tho

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

ikr

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

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

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

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

Good sort

well it doesnt use as much numbers so...

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

11:11

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

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

That’s at 12:58

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

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

thats terribly inefficient if it was real time

omg yes

Yeah

relatable

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

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

@@DragoStar 1 over n factorial

@@DragoStar 1 over nfactorial

My Guinea pigs in general

I’m glad someone had the same idea!

LMAO

Smooth sort actually roughened up the surface of the triangle

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

pigeonhole sort just built different

elements 1 and a really, really big number

“yeet”

The algorithms have learned to count

Galimantis 10:37 *

Count Count Sort

H O W

Est. Real Time: 391 microseconds.

no

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

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

Future me: *Yes. Yes you are.*

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.

nice 69th like

Omg ur right

And that’s without even talking about pigeonhole sort

@@Hasde_dfs tim sort

@@Hasde_dfstime stamp?

Wait til you see BOGOBOGO sort…

​@@locrianphantom3547with 10 inputs!!!!

Time Sort: Hold my beer

TimSort: Try me bitches

Pigeonhole Sort: Boom, done! What now?

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

pancake sort: merry christmas 2016!

It does tho

which

dubsteb

Obviary god damnit take my like

42th

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.

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

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

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

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

@@ironoat I know

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

9:58

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

Whoops, sorry.

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

Whoops! You have to put the CD in your computer

Gone Reduced to atoms

Seems not sorted yet

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

The algorithm wants to show off its family

nice pfp

That's their internal buffer!

Then there's Odd-Even

Base16 made some sort of rbg boss battle theme intro

@@icebearpl188 some *_sort_*

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!

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 :)

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

"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.

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

Except this is actually the worst case scenario

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

@@Fera-gr5mm That is true.

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

Tournament sort?

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.

Slow sort

@@lithiumwyvern_ ngl that's kinda genius

And it also sounds great.

it's trying is best

Why are you being so rude to min heap sort?

Leave min heap sort alone 🥺

Same

Are you from there future? What's it like in 2048?

So when I play 2048, I'm just being a very slow sorting algorithm?

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

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

Strong heap sort?

The fastest sorting algorithms ever: TimSort, Pigeonhole sort and Counting sort (.391, .573 and .889 milliseconds estimated real time, respectively). In practice though, only TimSort is in wide use (i.e. Python).

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 .

​​@@BigFatWedgeigeonhole? Or even timsort