Sorting is a fundamental necessity in computer programming, but not all sorting algorithms were “created equal”.

You probably know that the best complexity for comparison-based sorting is O(NlogN), but today we are going to discuss some revolutionary sorting algorithms that you better **avoid** using in your own programs.

Hold on to your seats, here are the most ridiculous sorting algorithms that you ever heard of.

### Bogosort

There are two versions for this algorithm, one is deterministic and the other is not — which means there is no bound for its runtime.

The pseudo-code for the algorithm is as follows:

while not is_sorted(list):

shuffle(list)

This one above is the non-deterministic version, we basically shuffle our list until we get lucky.

We can take advantage of the fact that a list of N elements has N! orderings, which means we can just check all of the possible orderings and report which is sorted.

This deterministic version has an average performance of O((n+1)!).

**Code for the algorithm:**

defis_sorted(data):

returnall(a <= bfora, binzip(data, data[1:]))defbogosort(data):

whilenotis_sorted(data):

shuffle(data)

returndata

### Stalin Sort

This one is one of my favorites, I even went as far as tweeting about it.

This algorithm just forces the list to get ordered in a sorted manner.

An element that’s not in the right order is just thrown into the gulag.

Stalin sort has an astonishing performance of O(n), highly recommend.

In case you find it somehow useful here’s the code in a copiable version

defstalin_sort(arr): if arr == []returnarr max_val = arr[0] sorted_arr = []forvalinarr:ifval >= max_val: sorted_arr.append(val) max_val = valelse: print(f"{val} sent to Gulag")returnsorted_arr

### Sleep Sort

Although this is far from an ideal sorting algorithm I find the idea pretty cool.

Given a list `[5,2,1,3]`

, we will dispatch 4 threads that will sleep for 5,2,1,3 seconds and print the time they slept for.

importthreadingfromtimeimportsleep items =`[5,2,1,3]`

defsleep_sort(i): sleep(i) print(i) threads = []foriinitems: thread = threading.Thread(target=sleep_sort, args=(i,)) threads.append(thread) thread.start()fortinthreads: t.join()

Sleep sort has the performance of O(max(input)+n) — quite a revolution right here.

These 3 sorting algorithms are the ones that I found the most amusing and interesting to cover, but there are many more of them.

Here’s a few more from xkcd, which some I found to be painfully true.

Leave a comment with your favorite and amusing algorithms.

Here is my Twitter.

Here are my other links.

## 3 responses to “Unconventional Sorting Algorithms”

My current fave: for each element, 3d print a bar that long (in parallel, with lots of 3d printers). Then take the sheaf of bars, put it end-up on a counter, and pull out the top one, then the next top, etc. O(n) + O(n/printers), with a very large constant. 🤪

LikeLike

Sounds like a Spaghetti-Sort (https://en.wikipedia.org/wiki/Spaghetti_sort) with a budget

LikeLike

It’s missing “lucky sort”. The only sorting algorithm that runs in O(1). Precondition: the list must be sorted. If the precondition is not fulfilled, the result is undetermined.

LikeLike