The FASTEST sorting algorithm: Part 1 - TimSort

This video explains the Tim sort algorithm, which is the default sorting algorithm in Java and Python. The Tim sort algorithm is a hybrid of insertion sort and merge sort, and has some optimisations to help reduce the total operations required.

We start by comparing various sorting algorithms and choosing a hybrid based on run time and asymptotic complexity. The resultant algorithm is faster than the naive merge sort or insertion sort approach.

In the coming videos, we will improve on the algorithm as Tim sort does.

#TimSort #Sorting #GauravSen

Social links:

[Errichto]

9:09 - If this expression is so small, we would just increase 64 to 128 or more to speed up the other part. The expression should be ci * 64^2 * N/64 because you run insertion sort N/64 times. Usually the constant is chosen in such a way that two parts of combined algo run in similar time each. If one manages to speed up any part, the whole thing will be faster.
Other than that, cool video.

[shivankchopra]

Amazing! Such a pleasing explaination, I didnt even noticed that how did these 13 mins passed by. God bless you!

[AsutoshSahoo]

loved the video, was searching for this topic few months ago, couldn't get video material, today your video pops up in recommendations. Liked the way you organized the topic into series, 1st giving a brief overview of the idea and inspiration behind the algorithm. Keep the videos coming. :)

[SansWordHuang]

Thanks for making this video. It's 2020 now and this is still pretty useful.

[yashashav_dk]

You are AMAZING! Love your enthusiasm. Keep up the great work Sir!

[armandomorales]

Hello!!
I love this topic, it is hard to find advanced material as this explained easily. So thanks a lot for your videos.

When i was investigating tim sort, i realize with a lot of testing that if you split the set of numbers by the sqrt root of the size of the set you compare less. You can see it, if you test it with big data.

[gavinxdsouza]

Hell Yeah, finally some content on Tim Sort!

[sportsdata]

just found some top quality on youtube.
Great buddy..

[mohitmishra]

Great Video Gaurav.. Big fan of yours.. Keep making such videos it helps a lot.. :)

[absence]

thx a lot, felt like this was the most informative among the others.

[ayushipillai]

😋😋 U are the only person who made the video on tim sort that really helps me a lot .
😂😂 And u are too cute

[vipulprajapati]

Can u make a series to start coding from scratch for noob like me... Explaining everything like greedy approach, knapsack, prime number through SOE and all!

[starlord]

Nice, will see it later have exams😐, keep up the good work

[austossen]

i'm liking your video and i'm following it. i would like the math to be more clear but let's see about your next video. i appreciate that you're the only programmer that has a real video on timsort, otherwise known as natural mergesort. also, it's not necessary to use insertion sort to beat the time complexity of merge sort. although that is a good point. as far as my intuition is concerned, you only need to exploit naturally occurring runs to beat mergesort. that already reduces the size of the recursion tree. but thanks again. and keep doing these videos.

[ishangupta]

Thanks for explaining this, there's hardly any good video about this topic out there.

[mohitgupta]

Thanks for sharing this. You are a really good teacher. 👌👌

[R_BNK]

Thanks for the Video, waiting for next part

[armandomorales]

Please then explain fibonnaci heaps and convolution on string patterns. It's poorly documentated and you explain so well!

[kaustubhkislay]

Great video... your efforts are appreciated. And hey this other day I was looking for an implementation of Stabbing query but the reading material wasn't great. Just a suggestion for you, if you could cover. Stabbing query basically is given some intervals and a point x, return all intervals having that point in it. If you already know some resource, you could also metion that.

[divyasingh]

It's a fantastic way for such arrays of data which have some sequence somewhere.. But it won't be so efficient on data like 30, 35, 25, 40, 20, 45, 15, 50.. Almost alternately increasing decreasing! 😐 although a nice effort to present something that we generally do not come across! Thanks!