3 Levels of Sorting Algorithms - FASTEST Comparison Sort! 

Just started a computer science degree at 44, long way to go. Great video but, thanks.

i didn't understand a single thing but still gave a like

I've watched hours of algo videos during the past few weeks and this video is thorough yet significantly easier to understand than most others. Thank you!

Based on the sheer volume of documentation on sorting algorithms, I honestly thought it would be a significant factor in my programming career. I doubt in the last 20 years I’ve ever sorted a single thing…. But still fascinating.

lvl 1 -O(n^2) - bubble, selection, insertion, lvl 2- O(nlogn) - merge , quick, heap

The main advantage of TimSort is that it works really well on partially sorted data. It's pretty rare to come across truly random data and when the data is already partially organised TimSort has the intelligence to skip over the already sorted sections while other algorithms will naively sort them. Also there should be an honourable mention to non-comparative sorts like Bin and Radix sorts. Radix, especially, can be incredibly fast when the sort keys are can be expressed as Integers with a known range. It's O(n) complexity, and while it does a lot of swaps, it has good memory locality which helps with cache misses.

Thank you for the explanation about insertion sort. There seems to be some conflicting information out there about if it is actually quicker or not in comparison to bubble or selection sort methods - I think the important distinction to make is that it is in fact faster than those methods in best-case scenario, and the same in the worst-case scenario - but in between best and worst-case, it is still potentially quicker than the other two.

For those who can't see the text at the end graphs, Introsort took 1st followed closely by Timsort and Quicksort in 2nd/3rd place respectively

I think it would have made sense to mention that these comparisons here are AFAIU based on the idea of equal access times to all elements. This is seldom through nowdays with several levels of caches and virtual memory. In the old days this was even more of an issue when the data was on multiple tapes where the seek times were enormous compared to anything else. I guess merge search is then then an important step in sorting as you can sort a section in main memory, write it out on tape and then read from several tape units one item, pick the largest one and write it all out as you go to yet an other tape unit. I'm not old enough to 'have been there done that', but old enough to see the step,stop operation of a large number or tape units in movies and I always suspected that was because of merge sortin. At least in many cases.

Radix sort?

I found Sedgewick's "Algorithms" to be great at going into lots more detail about sorts (and other things). That's where I also learnt that MergeSort and HeapSort came about because of using and building tree-oriented data structures.

Very underrated channel. Excellent content. Keep it up❤️❤️❤️

After watching this video, I remembered my lecturer who taught us those sorting algorithm in the same way as presented here, that is just reading from the slides. In the class, I pretended to understand everything and listen carefully, but in the end, I didn't understand anything.

It seems like someone could do analysis on which algorithm works best on what type of data (size, data type, % already sorted...), and just select the proper algorithm(s) to sort. For example, if it is known that algorithm A works best on almost sorted data and that condition is detected, then run algorithm A on it.

Wow that was quick. I would have liked to have seen the finish of the race.

Distribution sorts can get to the minimum time complexity of O(n). *Examples:* Bucket sort Counting sort Flash sort Pigeonhole sort Radix sort

You are way smarter than I am. You could have been speaking Latin. I didn’t understand a thing but you get the gold star from me. Dropping a like

nice overview and graphical representation! Thanks. Last time I thought about sorting algorithms was decades ago, I assumed current libraries would do something smart. Nice to hear what ;-)

Can you make a video on how you did the animations? I assume you programmed the timing specifically (one time unit for iteration)?

Thank you, just the video I was looking for after the last one, thanks for the info

I created an algorithm that sorts two numbers on their right place in one iteration. However you need a whole copy of the array with numbers and a few other variables. So basically a loop runs through the copied array once and saves the index of the biggest and smallest element in variables so you can access them. Then this smallest element gets written to array[0] (First) and the biggest to array[size-1] (last). 0 is represented by a variable and gets incremented After the next step. size-1 is also a variable and gets decremented after the next step. So you know where to put your next smallest and biggest value from the copied array. The inserted elements from the copied array are now written to -1 so they are „hidden“ for the next iteration since our smallest value needs to be 0 or larger. And this gets repeated until the bigger index in the real array is smaller then the small Index. Because then every element is sorted. Ill post Java code in a second. Hope this doesnt exist yet.

Don't mind me just watching videos to pass the time until bogosort has sorted the list

Does your example of bubble sort sort in ascending order while selection is descending or am I missing something?

This is Dope brother!

Plz a video on radix sort.

Insertion sort can be done O(N*log(N)) as well if you find the insertion place by comparing to the middle of the possible spots rather than the extremum. Say you have 1023 elements in the sorted part of your list, and the next one to insert is the 612th smallest. Instead of comparing to elements 1023, 1022, 1021 etc. until 611 of the sorted list, you compare to the 511th, then the 767th, 639th, 575th, 607th, 623rd, 615th, 611th, 613th, and 612th and after log2(1024)=10 comparisons you already know exactly where to place the new element. This keeps the advantages of insertion sort while guaranteeing the speed that quicksort can only hope and pray for

you forgot radix sot. given the proper linked list implementation it is in place, in order and O(n)

if sorting int without duplicates, sort by putting all elements into a boolean array(size = the largest element) and then generate an array according to that boolean array. if u want to remove duplicates after sorting, u can also use this method, the time complexity is O(1). if u want to keep the duplicates, link the elements into linked list. if u want to reduce the memory size, use hash function to deal with collisions(arr[i] % num)

Let it finish sorting!!

I wouldn't say that the heap is unsorted but partially sorted.

I came up with a sorting technique that runs zero comparisons. but requires a custom chip to run on. I doubt that trying to emulate the chip design would yield much in time savings.

After watching this, I was finally able to sort my life out

Why doesn't Insertion Sort binary search the sorted section of the list?

I just got into computer science AP classes and this video might as well be a horror show for me.

I "sort" of understand all of this.

Hello i have a question for an interview about what is the time running for the ''sort in '' method of an object, do you have any idea

the title says “FASTEST COMPARISON SORT”, but the thumbnail implies there’s one that’s faster than O(n log n)? isn’t that impossible with comparisons only?

How you created the graphs

Who can make a comparison between Introsort and Quicksort 'Magnetica'?

Long Story Short, It is Impossible to get below O(n*Log(n)) with normal sorting algorithms. There is a Mathematical way of prooving that, which has Something to do with how recursion works. However, there are other Specialized algorithms which Work in O(n), but with the difference that the sorting range must bei limited for Them. You can Imagine them Like a Container, in which you Store all possible elements, and then Go through the list which needs to become sorted. Every time you find an element, you Count +1 in your Container for the element you found, and Output the result in the end. That works for Limited Problems, but since you dont know the Elements which need to be sorted in Most cases, its Not used very offen.

8:50 It's sounds like these 2nd tier and hybrid all have a sorting time of O(N*Log(N)) so wouldn't that mean they were all the same speed?

Great explanation. Exactly what I was looking for. Thank you.

Although Shell sort is a variant of Bubble Sort but speedy, I think it would be worth to receive a mention.

This video is a gift from God.

How do I sort my socks with these algorithms?

Is there any benefit to using a slower sorting algorithm? Why wouldn't you go for the fastest algorithm whenever possible?

What do you mean by not stable ?

no RADIX sort? RADIX is incredible powerful on large datasets

glorious counting sort O(N) master race

O(n) is possible! Just not with comparison sorts.

Where are Kite for linux?

🎯 Key Takeaways for quick navigation: 00:00 🧭 *Introduction to Sorting Algorithms* - Sorting algorithms are crucial for various operations like search and database operations. 00:16 📊 *Levels of Sorting Algorithms* - Sorting algorithms are categorized into three levels: n squared complexity, n log n complexity, and hybrid algorithms. 00:31 🚀 *Level 1: n squared Sorting Algorithms* - Bubble sort, selection sort, and insertion sort are basic n squared sorting algorithms. - Bubble sort repeatedly compares adjacent elements and swaps if needed. - Selection sort divides the list into sorted and unsorted sections, selecting the smallest element. - Insertion sort iterates through the list and inserts elements into the sorted section. 02:51 🔍 *Level 2: n log n Sorting Algorithms* - Merge sort, quicksort, and heapsort are n log n complexity sorting algorithms. - Merge sort divides the list into sublists and merges them to sort. - Quicksort picks a pivot, partitions the list, and recursively sorts sublists. - Heapsort maintains a heap structure in the unsorted section while extracting elements. 06:53 💡 *Level 3: Hybrid Sorting Algorithms* - Hybrid algorithms like Tim Sort and Introsort combine features from multiple algorithms. - Tim Sort collects runs and merges them efficiently, optimized for nearly sorted data. - Introsort starts with quicksort, switches to heapsort for large lists, and uses insertion sort for small partitions. 08:58 🔄 *Conclusion on Sorting Algorithms* - Sorting algorithms have various characteristics, including time complexity, stability, and space requirements. - The choice of sorting algorithm depends on the specific application and data characteristics. 10:11 📚 *Closing Remarks* - The video summarizes the key points about sorting algorithms and encourages viewers to subscribe for more content. Made with HARPA AI

Nice :) Will refer others!

This video is about as much as you need to know about sorting as if you find yourself writing a sorting algorithm you probably on the wrong path. Use a standard libray insteand.

Third is O(color sorting). Not O(?)

Thanks , very useful.

Why the homie keep leaning over?

Why does nobody give bucketsort and pidgeonhole sort some love? :( Also bogosort. It's really fun to confuse students with it when they try to calculate the complexity.

I wonder how a learning AI would fare here. Would it end up with something close to introsort? Or something else altogether? IIRC it’s impossible to be faster than O(n log n) on average anyway.

internet explorer uses stable sorting is that slower than all those ?

we set up a facebook group for people really serious about learning Python or helping others with their learning journey facebook.com/groups/505658083720291

Hash sort, very quick

Why does nobody include bogosort as the deafult comparitor?

I know the definitions of all the words you're using, but I have no idea what you're saying.

bogosort is clearly the fastest, since it can sort everything in one try

Try bogosort with 1 planck time delay

What about wolfsort

great video! im assuming you have strong face gestures so you dont fall asleep mid sentance?

It would be better if the sortings in the final were separated by their level.

Ryan Ghosling??

Great Job! Thanks A Lot....

i was here 🔥

radix would win on random data in very big list...

3 Levels? In that regard, you forgot 2 types of sorting algorithms that are quite important, Bucket sort, which can be O(n) with known parameters, and Bogosort, which can be O(?) and really frustrating.

Dude u forgot LSD Radix Sort

Where to do these sorting? I wanna try it

Sleepsort uses the least ram

Bogosort is the best sorting algorithm.

Heap sort is o(n) space complexity because you need heap that will hold the whole data structre if it's not an array

You don't seem to know what the letter O stands for. It means "Order of" which means the magnitude of the number is a constant multiplied by the quantity. As an example, "O(n^2)" is pronounced "order of n squared" meaning the running time is a constant multiplied by n^2. One can count time, number of swaps, number of comparisons, memory usage, or any quantity which is relevant to the performance of the algorithm.

his face looks generated by an AI

you forget the lvl4 and the best one. the bogosort.

Wow a sorting video that doesn't cover radix sort expect for mentioning that its about comparison sorts in passing..... im shocked once again

Bogosort to the moon

Selam Ben Adal

lucky bogosort = fastest

Too much bobblehead and not enough sorting on screen.

You should skip explaining how algos work, because except for trivial alogs your are explanations are not good at all, but instead you better explain in what situation I would choose one or the other algo.

You forgot bogosort😂

Lv4 network sortation.

Yep. I didn't understand a single thing in this video

Radix sort: PATHETIC

yaaaaaaaaaaaaaaaaaaaaakkkkkkkkkkkk

No coding link to download and also very speed in teaching which is not understandable to all non english students. Please give the code links and also provide such PPTs and books Tutorials for free because if you provide more for the students then it will be very helpful