Code?
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)
Bogosort
Complexity: O(n * n!)
The classic sorting algorithm that has many aliases, among which are Permutation Sort, Stupid Sort, Slow Sort, and Monkey Sort.
Main idea of this algorithm is to randomly shuffle the elements inside the list until it is sorted. Thanks to Python’s built-in random module, we can implement it in just a few lines. Definitely much easier compared to implementing quick sort or merge sort.
This means there are n! possible combinations, and because for every iteration we will spend O(n) time to shuffle the list and another O(n) time to check if the list is sorted, we end up with O(n * n!) for the complexity.
Bogobogosort
Complexity: O(my God)
An advanced variation of the Bogosort. Bogobogosort thinks that the original Bogosort algorithm was far too efficient, that’s why it introduces extra steps to make the algorithm more complicated.
Bogobogosort will sort the first 2 elements of the list with bogosort and work its way up until all elements are sorted. After each bogosort, it will check if the next element is already in the correct order. If it’s not in the correct order, we randomise the list and go back to the first 2 elements again.
To see the original description and detailed analysis, you can visit this page.
Quantum Bogosort
Complexity: O(n)
Also known as Multiverse Sort, this is the ultimate Bogosort variation. Unfortunately, we couldn’t find a Python code for this variation, but here’s the pseudocode. (source)
In theory, creating n! universe branches would cost O(1). The O(n) complexity comes from checking if the list is sorted. We assume destroying universes which contain unsorted list costs O(1) too.
Miracle Sort
Complexity: O(???)
Behold, the sorting algorithm inspired by the following StackOverflow answer. Just ignore the title of the discussion, it is not relevant.
Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)?
"Eventually, alpha particles flipping bits in the memory chips should result in a successful sort."
I implemented a backoff mechanism for the miracle wait time to give an increasing chance of a miracle happening between checking if the list is sorted.
Using the code above, I have confirmed that this sorting algorithm actually works. For already sorted list, it returns in O(n) time. Though, I am still waiting for a miracle on non-sorted list.
Pro Tip: You can actually you replace the "Waiting for miracle..." message with a prayer of some sorts and call it the Prayer Sort.
Stalin Sort
Complexity: O(n)
Ah, a superior sorting algorithm that runs in O(n), inspired by this "tweet" from the non-profit social media Mastodon.
"… Any element which is out of order is eliminated…"
The algorithm will go through the list once and remove any element that is out of order – either ascending or descending. It will always produce a sorted list in O(n) time at the end, albeit the possibility of a few missing elements.
Thankfully, there is a variation of Stalin Sort that actually keeps all the item inside the list. The idea is to push elements that are not in order to the front of the list, and then repeat this step until the list is sorted. Unfortunately, it didn’t run in O(n) time, which means it is inferior compared to the original Stalin Sort.
Thanos Sort
Complexity: O(n log n)
One of the more contemporary sorting algorithm inspired by Marvel’s Thanos’ philosophy. We implement a special function called snap() to eliminate half the member of a list at random.
The idea is to check if the list is sorted. If not, then we will snap the list and then check again if the list is now sorted. Repeat until the list is actually sorted.
Checking the list will take O(n) time, and thanks to the snap() function cutting the element by half every time, it will take O(log n) for every iteration. Both of those things considered, this algorithm has O(n log n) complexity.
A variation of the Thanos sort is the True Thanos Sort, in which we do one snap() function call without checking if the list is sorted. This operation will help future sorting by cutting the number of element by half.
Intelligent Design Sort
Complexity: O(1)
Intelligent Design is a belief that a Creator creates certain things or events inside the universe by design.
Assuming that all elements of the list are unique, there are n! possible combinations where n is the number of elements in the list. This means that the current order appears only 1 in n! cases.
The Intelligent Design sort believes that this occurrence means the Creator has sorted the list in such a way that it transcends our understanding of ascending and descending order.
Other naming and philosophical variations of the Intelligent Design Sort are as follows.
- Zen Sort: where you realize that the array, like all things, is ephemeral and its order is insignificant so you just leave it like that and pursue enlightenment instead. (source)
- Trump Sort: the array is always sorted. Anyone who says otherwise is fake news. (source)
Sleep Sort
Complexity: O(max(input) + n)
Another classic infamous sorting algorithm. The main idea is to sort the list by assigning the values to a sleep timer. When the timer finishes, it will add the value to the result list.
Larger values will have longer sleep timer, so they will be added after the smaller values, resulting in a sorted list in ascending order. If we need a list in descending order, we can simply reverse the list order using result[::-1]
The downside is that this only works for numerical lists. Oh, and it can also run for years if you try to sort very large numbers.
Stack Sort
Complexity: O(depends)
No, there is no code for this one, but you can visit this page to try it yourself. Now, you might think that this algorithm somehow uses a stack to sort the elements based on its name. That is incorrect.
Stack in the name is short for StackOverflow. Yes, that’s right, the Stack Sort will randomly crawl the top answers of StackOverflow questions tagged with javascript and sort
If you visit the Stack Sort page, it will try to extract a function from the StackOverflow answers, compile it, and then try to sort the input with that function. The best part? You don’t need to code, and it will tell you which answer is actually being used.
The complexity depends on your luck with the crawler. I have had some luck with successful sorting using this answer and this other answer, even though the latter returns a list of string instead of a list of integer. Some code successfully compiles but still failed to sort.
Code? is a series of humors related to data science and programming. They might not be useful for your daily work, but they might be useful to make you smile. Get regular updates on new stories and become a Medium member to read unlimited stories.
