Explaining EVERY Sorting Algorithm: Variants and Hybrids

This is the 3rd episode in my series explaining every sorting algorithm. In this video, I explain the most widespread hybrid and variant sorting algorithms.

Chapters:
0:00 Why Hybrid Algorithms?
2:36 Quick Sort with LL Pointers
3:01 Dual Pivot Quick Sort
3:55 Proportion Extend Sort
4:42 Intro Sort
5:23 Pattern-Defeating Quick Sort
7:08 Tim Sort
8:56 Iterative Merge Sort
10:00 In Place Merge Sort
11:12 Weave Sort
11:30 Rotate Merge Sort
13:01 Quad Sort
14:40 Block Sort
16:18 Weak Heap Sort
19:09 Smooth Sort
22:35 Poplar Sort
23:05 Ternary Heap Sort
23:39 In Place MSD Radix Sort
24:57 Binary Quick Sort
25:21 In Place LSD Radix Sort
26:05 American Flag Sort
27:10 Burst Sort
27:34 Spread Sort
28:31 Sample Sort
29:18 Proxmap Sort
29:37 Cartesian Tree Sort
30:09 Stalin Sort
31:16 Sleep Sort
31:36 Miracle Sort
32:00 Bogobogo Sort
33:04 Power Sort
33:50 Identity Crisis Sort
34:20 Outro Sort

#sorting #algorithm #computerscience

[PretzelBS]

It’s like I’m going shopping for sorting algorithms

[JeffHanke]

Great video! I especially like how you used Stalin sort as an excuse to talk about the longest increasing subsequence.

[Mitsunee_]

I tried to do a merge sort variant which partitions by basically doing "stalin sort" but instead of deleting it moves unsorted elements into a new sublist, which is then sorted recursively and merged with the already sorted list. In theory an already sorted list should be O(n). I also just realized an improvement, it might be nice so save the index where the first unsorted element was extracted to skip the first few comparisons in the merge step too. I didn't really look into improving it much since it's rarely better than regular Merge Sort for randomized test arrays.

[ouroya]

love your videos! they are very clear and concise, and i especially appreciate that you explain benefits AND drawbacks, as opposed to just benefits

[maadneet]

10:42 I know it's not covered here, but the O(n^0.5) space combine-halves is one of the block sort variants, aptly named sqrtsort!

[Kuvina]

What's your favorite algorithm?

Leave a comment or reply. Mine might be shell sort because of its extremely small code size, and unique non integer power time complexity!

[styleisaweapon]

I like how a lot of algorithms fall back on either heap sort or insertion sort, almost like you should just use a heap instead of a list.

[onepersonintheuniverse]

Wake up babe, new Kuvina Saydaki sorting algorithms video just dropped!

[PhantomKING]

Idk what this would be named, but hear me out:

One of the most efficient sorting algorithms ever created, bogosort, wastes some time, mainly in three steps: checking if the list is in order, randomising it and finishing. Miracle sort solves this partially by eliminating the very time-consuming step of randomising; however, it has come to my attention that checking if the entries are ordered is itself quite time-consuming.

The new and improved bobo sort (from the Spanish word "bobo", meaning "dumb") just randomises the list and outputs it, then repeat. It is probably at some point going to give the right answer. The program may not terminate (specifically, it doesn't terminate for lists with mire than or equal to 1 possible ordering), so be careful when implementing.

[popahglo]

A new Kuvina upload is a good time to be had

[joda]

Love your visualizations and nice explanations. Also, though i don't know if it's on purpose, but your voice always places emphasis just where it needs to in order to keep my attention. Like, your inflections are really attention keeping.

[EA-nnfn]

Great video, thank you for putting light on some of these cool combination algorithms. i'm happy your channel has been doing well, you make great informative stuff!

[vinccool]

I’m here for the joke sorts, but still learn the legit ones.

Btw, really happy to see the joke sorts I’ve suggested.

[temmie]

I’m nb so I’m happy that I found someone who likes science and math :3

[brainboy]

Boho sort: I’ll just try again! (Randomizes the list) no, still not sorted. (Tries again)
Miracle sort: is it sorted? No? I give up.

[smaybius]

On proportion extend, finding the median without sorting the list first is possible, but only if the list is only of integers, and finding it takes O(partition) time. Optionally, the current item is comp-swapped with an adjacent item during the search, which makes it called bubblescan quicksort

[danield]

I'm currently very tired, but I just had to watch this video before going to bed because your other two videos have already been amazing. I was definitely not awake enough anymore, though. xD

[TaranVaranYT]

I have been thinking of a sorting algorithm called Spread Sort. The process goes like this:
If the list size is even:
1. Take the 2 items in the center of the list and move them to the outer parts of the list.
2. Repeat the same with the 2 adjacent to the center. Continue doing this until you reach the outer parts.
3. Reverse each sequence of items in groups of increasing size (starting at 2) including those that get cut off.
4. Once you reverse the whole list (when group size = list size), check the 2 values at the left, and swap them if the left one is larger, then move the point of focus to the right by 1, and swap those. Keep doing this until you swap the 2 rightmost values. Continue doing Bubble Sort like this for 1 more cycle.
5. Do steps one and 2 again.
6. Check for sublists, and extract the one with the most consecutive items (an item has to be equal to the ones on both sides give or take).
7. Group the extracted sublist with the item that is 1 less than the smallest one. Repeat steps 1-7 until the sublist is the same size as the main list itself.

If the list size is odd:
1. Take the 2 items next to the center of the list and move them to the outer parts of the list.
2. Repeat the same with the 2 adjacent to those. Continue doing this until you reach the outer parts.
3. Reverse each sequence of items in groups of increasing size (starting at 2) including those that get cut off.
4. Once you reverse the whole list (when group size = list size), check the 2 values at the left, and swap them if the left one is larger, then move the point of focus to the right by 1, and swap those. Keep doing this until you swap the 2 rightmost values. Continue doing Bubble Sort like this for 1 more cycle.
5. Do steps 1 and 2 again.
6. Check for sublists, and extract the one with the most consecutive items (an item has to be equal to the ones on both sides give or take).
7. Group the extracted sublist with the item that is 1 less than the smallest one. Repeat steps 1-7 until the sublist is the same size as the main list itself.

[jean-michelgilbert]

Some implementations of intro sort actually use insertion sort for list sizes under 32.

[olive]

I actually burst into laughter when you explained sleep sort