Tim Sort

Visualization and "audibilization" of the TimSort algorithm.
Sorts a random shuffle of the integers [1,100] using TimSort (standard sorting algorithm in Python, Java SE 7 and on Android). See en.wikipedia.or... for an explanation. The C++ implementation from github.com/gfx/... was used.
After the slow sorting of [1,100], the algorithm is run again faster on [1,1260].
More information on the "Sound of Sorting" at panthema.net/20...

[@Crossark1]

AND HIS NAME IS JOHN CENA! 0:39

[@slowsloth3809]

Crossark1 HOLY SHIIIT Edit : 0:53 Pacman ate a ghost.

[@Welowas]

I didn't laugh out loud but this is still fucking hilarious.

[@raffimolero64]

1:06 the REAL pacman ate a ghost.

[@AidenOcelot]

Crossark1 how do I like a comment twice!?

[@slavaxkt5997]

lmao

[@AAAAAAAAAA42]

Thanks Tim

[@jeongheonlee4556]

A bastard born between merge sort and insertion sort

[@kaylamitchell1982]

Not the best parts combined, the worst ones.

[@RipleySawzen]

@@kaylamitchell1982 Actually it's the best ones

[@nsq2487]

@@RipleySawzen Dude it's so fucking slow. Worst parts, definitely

[@RipleySawzen]

@@nsq2487 How can you not even realize this is slowed down so you can actually see it? If it were in real time the entire video would be LITERALLY ONE FRAME. This would still hold true if there were 100 times as many entries to sort.

[@nsq2487]

@@RipleySawzen The way the video is slowed down is by adding a fixed delay after each comparison. Yes the process is dramatically slowed down for us, but it's still representative of the actual time it will take for the sort. What appears slow to us will also be slow in real life.

[@ayior]

And here I thought the person who uploaded this video came up with a new sorting algorithm and sorta named it after himself

[@dlwatib]

A very good stable hybrid sort for modern machines with plenty of memory. Performs well on all input data [best case O(n), worst case O(n log n)] but uses O(n) extra space.

[@Manuel5975p]

It's best case n log n

[@nahrafe]

@@Manuel5975p nah it's O(n), O(n log n) would be original merge sort.

[@Manuel5975p]

@@nahrafe hmmm, is the merge step different from the original?

[@lucass8119]

@@Manuel5975p best case is if array is already sorted. Tim sort will divide array based on segments that are all already in order and will then merge them. If it is all in order, no merge will be done, therefore linear time

[@domjanabi6006]

1:49 when someone repeats something slowly to me expecting me to understand what they're talking about

[@blackapple2938]

hi my name's tim sort

[@davidegaruti2582]

My name is sort ... Tim sort

[@NoMoreForeignWars]

Tim pool made this.

[@raymondhettinger9603]

Thank you for the visualization. I have one important request though. Can you publish another video but with a dataset that shows-off the winning feature of Timsort which is taking advantage of partial orderings in the dataset. In other words, Timsort mainly shines with real data and isn't anything special when confronted with pure random numbers.

[@frempy4426]

No

[@snazzysportstacker]

i only listen to real music

[@FranklyNorman]

Hands down the best video game I’ve ever played.

[@Kidboo377StudiosGaming]

This is almost just like the merge sort.

[@MADMACHlNE]

That's because the Tim sort is just a smart merge sort that can tell when it would be more efficient to switch over to an insertion sort.

[@TheLujamusic]

Bottom-up mergesort to be exact

[@VY_Canis_Majoris]

There’s no one in your contacts matching ’Tim Sort’.

[@dannyundos8927]

I still don't know what "galloping mode" is, though.

[@alexjago51]

You might've learned in the three years since, but it basically just exploits cases like where the smallest value in the A side of a merge is bigger than quite a few values in the B side (or vice versa). So the 'galloping' refers to the search process of where to insert the first A-side value after the B-side run.

[@saopy]

Thank you Tim, very cool!

[@JackLe1127]

so correct me if i'm wrong. Tim sort is technically merge sort with the base case of the minimum size of a run. a run will then be sorted using a different sorting algorithm?

[@smaybius]

Runs are created using binary insertion sort just like with std::stable_sort. It's also adaptive and can flip reversed groups and detect how sorted groups sre

[@ona512]

Did I accidentally turn on Everything Is Going To Be Ok

[@philipnelson5]

Why would you tim sort random data?

[@0Namington]

Because it's cool.

[@fubarhandle]

Came to the comments for this.

[@user-ix9lw1te8j]

its for visualization purposes

[@RipleySawzen]

What would you suggest?

[@Reza_Alizade]

Yes Timsort must be shown on data included some sorted ones

[@karamboubou8579]

This is basically weave sort/merge + insertion sort

[@asafkaya9227]

Thank you. Now I am addicted.

[@anastasiadunbar5246]

1:51 Sounds like a crying baby.

[@freedom_is_in_your_mind]

Не знаю, как я попал сюда, просто проснулся в 3 часа утра и решил сделать запрос в гугл "аэродинамика коровы"

[@orinzyze7625]

shoutouts to all the tims out there

[@RonWolfHowl]

Insertion sort to a certain length, followed by merge sort.

[@user-pi8bm3pw1b]

looks like a merge but sorting is little different

[@sutterismine]

.sorted() python function behind the scenes!

[@Axadn]

so satisfying

[@OrhanGHafif]

Explains better than the paper. (Entry nick uyumu yazıcam ama kim gelecek de görecek asdasdas)

[@AzureLazuline]

I was expecting an explosion sound at the end

[@skandragon586]

Ive been watching these sorts and i was wondering how you end up with two copies of some elements in the list? Like at 0:50 there are several of the lower elements being duplicated onto the left side before being removed from the center/right

[@ME0WMERE]

It's slowly replacing the list shown with the sorted section of the list in auxiliary memory

[@tomergngn]

it might look the same for the naked eye, but they are slightly different. It uses an algorithm called "Merge Sort" (Time Complexity O(n + m)). It checks which value is lower every time and puts it next on the list. because in this video the values are very similar, the merge sort will run into many close numbers, which in the speed it's moving and in the lack of better eye equipment will look the same to you.

[@ME0WMERE]

@@tomergngn at 0:50, where do the middle values go? Exactly. They are being overwritten by values from auxillary memory.

[@tomergngn]

@@ME0WMERE oh you're right, I was wrong. I thought that's what the algorithm did, my bad

[@want-diversecontent3887]

Tim sort: Insertion sort, merge…sometimes backwards

[@solar.mp3]

0:35 sounds like a tune

[@jercki72]

it's an insertion sort combined with a merge sort

[@FirstNameLastName-bq9hs]

man, i enjoy this video

[@user-mf9mk9kt8p]

0:28 How the bars disappear and re-appear?

[@legoshaakti]

It’s writing them to a second array

[@Ambipie]

Like putting pencils into a case

[@thaongan3445]

Tim sort is the sorting algorithm combine by insertion sort, merge sort or something else?

[@argentonath]

Tim sort is a smart hybrid of merge and insertion sort. It takes advantage of already sorted runs that often exist in real world data. If they're too small, it uses insertion sort (which is very fast when applied to small lists) to make bigger runs. Then it merges sorted runs, which is faster than merging unordered lists like traditional merge sort. If you're curious about the details, google "timsort.txt" and you'll find Tim's original description (or look on python's issue tracker for issue 587076, where it is attached)

[@eduardo.chaves]

Timsort vs quicksort, which is best and when to use which?

[@WaterCrane]

A better one is Timsort vs. Introsort (although simple quicksort works too). Introsort is best when you want speed. Timsort is best when stability is the priority (elements with the same key value retain their order), but still want speed.

[@DriftHyena]

This is some poltergeist level sound shit

[@microman502]

nice job tim

[@_lapys]

I've seen this software somewhere... From the Hopson KZbin channel?

[@RammusTheArmordillo]

The second part sounds like alien music

[@sergeymurtazin1416]

I love you videos!

[@RaccoonPower]

Gnome Sort 2.0 + Merge Sort

[@Huffy-dl6mi]

I'm disappointed because it didn't show it's collection of toys and go "heh"

[@violetvoxel]

Sorting from the Nile.

[@ALLCAPS]

looks like merge sort and slow sort combined. lol

[@teeth.2162]

May be my favourite sort. Until I find another sort that is better.

[@MarkAnthonyLaureta]

The operation seems expensive af

[@amey7064]

When you realize there's a 50ms delay, else...

[@user-hj2ft3du9g]

amazing!

[@miso-ge1gz]

some kind of weird mergesort?

[@theblob2937]

This reminds me of 2048

[@tropicbliss1198]

list.sort()

[@BulGoogol]

That look like merge sort

[@boofy1347]

real

[@ImBowsa]

Tim 👍

[@1024det]

TIMLIBIADEO! TIMMAH!

[@cvItist]

Faith soundtrack

[@DanChou626108]

awesome!

[@doc736]

Think I've found the perfect ringtone for my phone

[@brkrab8818]

nice clip

[@gamesstar-zs5qe]

Visualization

[@mistermoee]

merge sort 1/8 version

[@demensdeum_live]

лютый

[@triclamite]

tim

[@joeshoesmith]

This is basically merge sort tho

[@RipleySawzen]

But faster

[@jakerussell135]

merge sort but it starts with larger chunks and does an insertion sort for them

[@Cpt.C]

why is it so funny?

[@dabbingsquidwart2434]

Man, tim is loud.

[@Shmark]

1:57 ᵗⁱᵐ....... *Soooooooooooooooorₜ*

[@juliagiacomelli9056]

Could someone try to explain the Timsort algorithm or indicate a site to me? I have to make a research about it, but I haven't found almost any information...

[@tttc]

Go to its Wikipedia page, that is listed in this video's description, and read through it. Also read the links listed under Further Reading and External Links.

[@tttc]

No idea what you mean mate.

[@jamescaldwell2592]

username Why would it ever be an ulterior motive... it's a fuckin sorting algorithm...

[@connorconnor2421]

*_hEy TiMoThY!_*

[@GumRavil]

Я залип

[@want-diversecontent3887]

You're not supposed to use it on random data.

[@user-um7zf4le1p]

0:49

[@user-nx4su4sw7h]

Кросивое

[@KakoSchwartz11]

Python

[@CrazyTankersVN]

I am merge sort but cooler...

[@Timur_Koniakin]

залип

[@Tracy_AC]

So is this insertion sort in the beginning just to get the data semi-ordered, and then merge sort?

[@danieldelizaur8613]

it is a bit more complicated than that. Timsort searches for already sorted subsequences called "runs". If the runs are smaller than a certain value, called "minrun", insertion sort is used to balance the lengths of the runs. then the algorithm uses a modified version of merge sort in order to get the sorted array. Note that sometimes the direction of the merge changes and only a half part of array is being copied to the auxiliary array. There are other things like "galloping mode" that boost the sorting in some cases, but they are complex to explain. That's all I know.

[@LittleFarmLife1637]

00:00:30 🍭🍭🍭🍭🍭🍭🍭🍓🍓🍓😻😻😻😻😻😻😻😻😻😻😻😻😻🦄🦄🦄🦄🦄🦄🦄🦄🦄😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻

[@VoidGravitational]

wtf

[@supercena163]

卧槽 炫酷狂拽吊炸天

[@walclow8247]

that's kinda horrible!