The FASTEST sorting algorithm: Part 1

No video

The FASTEST sorting algorithm: Part 1 - TimSort

Рет қаралды 57,186

5 жыл бұрын

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:
/ gkcs0
www.quora.com/...
github.com/gkc...

Пікірлер: 105

@Errichto 5 жыл бұрын

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.

@gkcs 5 жыл бұрын

That's correct! Haha, dunno how I missed that 😛

@vikas6024 4 жыл бұрын

wow Errichto is here!!

@mykhailo_chaus 4 жыл бұрын

Can't get why two parts should run in similar time? Looks like we should solve optimization problem *min_x {C_m * N * (log N - x) + C_i * 2^x * N}* for each N. For very large N solution approaches some fixed number which depends on C_m/C_i fraction. Hence, the first part will grow while the second remain constant.

@sarimkamal5649 3 жыл бұрын

@@mykhailo_chaus because if anyone of the part is slower we can replace its some of the computation with the faster part of the algorithm to make the overall runtime faster. hence we can only optimize until both are equal.

@shivankchopra7429 5 жыл бұрын

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

@gkcs 5 жыл бұрын

Thanks Shivank!

@AsutoshSahoo1 5 жыл бұрын

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

@gkcs 5 жыл бұрын

Thanks! 😁

@SansWordHuang 3 жыл бұрын

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

@gavinxdsouza 5 жыл бұрын

Hell Yeah, finally some content on Tim Sort!

@armandomorales6959 5 жыл бұрын

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.

@gkcs 5 жыл бұрын

Thanks! That sounds like an interesting idea. Maybe you could blog about it in detail sometime, I'd like to read that 😋

@yashashav_dk3766 5 жыл бұрын

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

@gkcs 5 жыл бұрын

Thanks :D

@ishangupta5045 5 ай бұрын

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

@absence9443 3 жыл бұрын

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

@mohitmishra6142 5 жыл бұрын

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

@vipulprajapati8641 5 жыл бұрын

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!

@ayushipillai5923 2 жыл бұрын

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

@sportsdata5018 2 жыл бұрын

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

@shriya6755 2 жыл бұрын

Informative

@alessandropandini4774 6 ай бұрын

I'm sorry, but by heart beats for that mf'er of BogoSort, I love the thrill you get when you realize it could either take literally forever to correctly sort a normal deck of cards for your midterm project or end it in as little as 1ms with 1 comparison and 1 array access XD Seriously though, great video

@audunoklevik4435 Жыл бұрын

Good explanation!

@aungkyawkhant321 Жыл бұрын

This video is amazing!

@gkcs Жыл бұрын

Thank you!

@austossen 4 жыл бұрын

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.

@starlord9220 5 жыл бұрын

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

@R_BNK 5 жыл бұрын

Thanks for the Video, waiting for next part

@mohitgupta6613 5 жыл бұрын

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

@gkcs 5 жыл бұрын

Glad it helped 😁

@sterben04 3 жыл бұрын

Nice explanation

@DevThaWrightOne 4 жыл бұрын

Very good explanation! Thank you.

@raviraj8209 4 жыл бұрын

this is gem , thanks a lot

@kaustubhkislay3126 5 жыл бұрын

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.

@gkcs 5 жыл бұрын

Thanks Kaustabh! I'll have to look into this :)

@armandomorales6959 5 жыл бұрын

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

@gkcs 5 жыл бұрын

I'll have a look at these 😋

@codediva007 4 жыл бұрын

YEY. .. ENJOYED THE VIDEO. THANKS.

@gkcs 4 жыл бұрын

Thanks!

@swatisharma765 5 жыл бұрын

Cool!

@lovlinthakkar3308 5 жыл бұрын

Amazing! Great explanation.

@divyasingh7211 5 жыл бұрын

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!

@gkcs 5 жыл бұрын

That's true, but it is handled too. We will see that in the next videos :)

@arifurrahmanrabbi1338 5 жыл бұрын

For this you get the condition of merge sort. A single element as the sorted sequence. So it will be at most as bad as the merge sort for the worst case. But on good cases it will be better than merge sort.

@gkcs 5 жыл бұрын

That's right :)

@pratikjain4704 5 жыл бұрын

You are awesome Gaurav!

@gkcs 5 жыл бұрын

Thank you!

@rajatpal1019 5 жыл бұрын

very nice explanation.

@vaishnaviboje 3 жыл бұрын

I didn't get contents on tim sort... Thanks for your effort

@techfornoobs4241 5 жыл бұрын

wow, this is awesome. how long did it take you to learn all this stuff?

@gkcs 5 жыл бұрын

It's been a few months since I started the 3 "deep" topics: Tim sort, Git Internals and Garbage collection. I am nearly done editing this. Hopefully the other two will be edited faster 😁

@viraj_singh 5 жыл бұрын

great video as always

@gkcs 5 жыл бұрын

I'm happy to hear that! 😁

@SujeetGupta-hx6sl 5 жыл бұрын

Nice , when is the part 2 getting published on KZfaq ?

@gkcs 5 жыл бұрын

Coming soon 😋

@nicholasdavidowicz9832 2 жыл бұрын

I don't really understand why we don't use mergesort instead of insertion sort. The other parts of timsort require min(n,m) aux space for merging the runs, so it seems trivial to also use that space for a mergesort. Isn't the space complexity the only argument for insertion sort vs merge sort? Am I missing something?

@Shankar_-rl1cp 2 жыл бұрын

I gussed about merge ..after chunked pices sorted by insertion

@justanotheryoutuber739 5 жыл бұрын

Is there no minimum amount of elements for each section in tim sort? meaning that even if you have a small sequence of sorted numbers (let's say 1,2,4) you would still need to match a minimum amount of elements (let's say 5) and would therefore have to instead look at all 5 elements and sort them with insertionsort

@prateekkanujiya9775 5 жыл бұрын

Could you please add some videos on DESIGN PATTERNS

@amitagnihotri30 5 жыл бұрын

Apparently "bhai ka video" is much awaited then "Bhai ki movie" :D

@gkcs 5 жыл бұрын

Bhai bhai bhai :p

@jugnuisfit1648 5 жыл бұрын

thank you for this video

@gpprudhvi 5 жыл бұрын

Cool video :)

@gkcs 5 жыл бұрын

Thanks!

@RegebroRepairs 5 жыл бұрын

There's very little information about TimSort, because it's not based on an abstract idea from a PhD student at some university, but written to be actually fast in real world apps. :-)

@gkcs 5 жыл бұрын

That is....true 😛

@ManishKumar-je2zp 5 жыл бұрын

Were you at The Fisherman's Wharf last Friday?

@hadarmanor12 2 жыл бұрын

please do about divsufsort where is not information about ittttt

@tamannagoyal8953 5 жыл бұрын

can u please make a video again for time complexity ?

@gkcs 5 жыл бұрын

It's mainly explained in this... But the other videos will go into more detail, of course :)

@anandkulkarni2111 4 жыл бұрын

Two questions at point 04:55. a. Why would you say that heap sort has poor locality of reference : Although binary tree [ which is node based ] has poor cache performance since each node is allocated on heap which is dispersed around and lacks cache coherence provided by arrays. A binary tree representation in place in the array is used in heap sort to perform the sorting, so why it has poor locality of ref ? in fact any lookup in array by index is O(1). b. Given (a) holds why would then constant factor 'C' hurt at all ?

@gkcs 4 жыл бұрын

a. Have a look at what locality of reference means. b. (a) does not hold.

@anandkulkarni2111 4 жыл бұрын

@@gkcs I Looked at definition of "Locality of Reference" in wiki and essentially the point i am trying to convey is that in array representation of binary tree should make pref etching much better than what could have been it it was a binary tree actually [ for the case of heap sort ]. The wiki says "such as, traversing the elements in a one-dimensional array are great cases for optimization via caching and pre fetching." in fact left child and right child of any node are sequentially present via indices 2*i+1 and 2*i+2 [ i being index of parent node ]. Could you kindly explain in detail the reason ?

@gkcs 4 жыл бұрын

Processors predict an index jumping forward one by one (i to i + 1, not i to 2*i). The page mentions "One-dimensional array are great cases for optimization via caching and pre fetching." because they are. But when you are going ahead in a linear fashion. Why do you think 2-D arrays aren't great for pre-fetching? They are stored as 1D arrays in memory, and a single jump along the column breaks the processors expectations.

@natture 5 жыл бұрын

Is there any predefined function in java for tim sort

@gkcs 5 жыл бұрын

Yup, Arrays.sort() does the job 😉

@natture 5 жыл бұрын

thank sir

@snehalkhandve9432 5 жыл бұрын

Can you please make a video or two on FIBONACCI SEARCH . Tried finding a lot of resources but couldn't understand completely.

@ashutosh.sharma 5 жыл бұрын

Thanks for the sharing this with us. I got a question - 10:03 how will we find those chunks? won't looking for them increase the time complexity (as we have to go through the data to see the order)?

@gkcs 5 жыл бұрын

The details are coming up in the next videos, stay tuned 😋

@ashutosh.sharma 5 жыл бұрын

@@gkcs looking forward to it😊

@abhijeetkrishnan 5 жыл бұрын

Wait, why is insertion sort the best sort for small arrays? Why not selection or bubble? Going by your analysis of the constant factor, bubble sort would require more swaps than insertion, but it has good locality of reference (comparable to insertion sort probably); selection has fewer swaps than insertion, but poorer locality of reference, since swaps are across large portions of the array - how does this make insertion better than selection? Does the better locality of reference dominate the higher number of swaps in deciding the better algorithm?

@gkcs 5 жыл бұрын

Two words. Empirical. Data. When in doubt, try them all and then reason about why it is the best. Insertion sort is the best because the experiments have proven so.

@SansWordHuang 3 жыл бұрын

@@gkcs I think the definition of "locality of reference" is different between you two, and @gaurav use the definition modern processors used. The point is processors tends to pre-fetch the next value you want to compare in insertion sort. and to locality is for reading/scanning array, instead of the swapping part. correct me if I'm wrong. and love your work. thanks for making this video.

@crazyprogrammer2795 5 жыл бұрын

great

@tkdevlop 5 жыл бұрын

What about JS one arr.sort(lambda) and c++ one std::sort(it.begin(),it.end(),lambda) what they use under the hood? I only know the Time complexity is Onlogn. Awesome video as always.

@bluefog68 5 жыл бұрын

GCC (libstdc++ to be exact) uses Introsort : www.geeksforgeeks.org/know-your-sorting-algorithm-set-2-introsort-cs-sorting-weapon/. You can see the exact implementation here : github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1952

@sonalinaresh7013 5 жыл бұрын

Happy birthday :)

@gkcs 5 жыл бұрын

Thank you 😋

@CodersField 5 жыл бұрын

Hi Everyone :) :) #50shot

@gkcs 5 жыл бұрын

Hahahaha

@randomnobody660 4 жыл бұрын

Sorry but isn't quicksort O(n^2)? I don't mean to be rude but big O notation is for upper bound. Quick sort has a worst case of n^2

@gkcs 4 жыл бұрын

You are right. The chance of n^2 is really low, if the pivot choice is randomized. Still, the worst case is as you pointed out: O(N^2)

@randomnobody660 4 жыл бұрын

@@gkcs Wow, thanks for the reply. I'm actually a little confused now. I seem to remember that o was for upper bound, omega is for lower bound, and theta is for tight bound (and indeed when I check wikipedia for mastery theorem for example i did not remember wrong). If this is the case there is no "worst case is O(n^2)" because O() always implies worst case. However I see many different sources (such as wikipedia on quick sort) that says "worst case: O(n^2) ... best case: O(n log n)". Should that not be "O(n^2) Omega(n log n)"? Or has the meaning of the notation changed?