## When quick sort is too quick

When you hear of sorting algorithm, which one pops up first in your head? Quick sort? Merge sort? Bubble Sort?

Back in university, one of my professors always told the class that quick sort is like the Apple of sorting world because they are very good at marketing. By naming itself “quick,” people associate them with being the fastest sorting algorithm even when merge sort is actually faster for average cases.

Setting that false advertising aside, I am pretty sure you have heard of those algorithms. Let’s move on to more recent ones.

Python uses Timsort, a hybrid algorithm derived from merge sort and insertion sort. The name Timsort comes from the author, Tim Peter, who created it back in 2002 for Python.

For specifically positive numbers, we have Radix sort. It is a combination of counting sort and black magic to manage a complexity of O(d*(n+b)), where d is the number of digits in the list, n is the number of elements in the list, and b is the base used which is normally base 10.

More recently in 2020, a new algorithm called Quadsort emerges. It is a 1500 lines implementation of a hyper-optimized merge sort that is capable of beating Timsort in multiple cases. The author is kind enough to provide visualizations and benchmark for us mere mortals.

You might think we will dive deep into the 1500 lines for Quadsort, but you will be mistaken. We are here to take a look into sorting algorithms that are more… interesting.

esoteric · ɛsəˈtɛrɪk
very unusual and understood or liked by only a small number of people, especially those with special knowledge (source)

Complexity: O(n * n!)