# Unconventional Sorting Algorithms

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:

`def is_sorted(data):    return all(a <= b for a, b in zip(data, data[1:]))def bogosort(data):    while not is_sorted(data):        shuffle(data)    return data`

### 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

```def stalin_sort(arr):
if arr == []
return arr

max_val = arr[0]
sorted_arr = []

for val in arr:
if val >= max_val:
sorted_arr.append(val)
max_val = val
else:
print(f"{val} sent to Gulag")

return sorted_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.

```import threading
from time import sleep

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

def sleep_sort(i):
sleep(i)
print(i)

for i in items:

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.

### 3 responses to “Unconventional Sorting Algorithms”

1. Gary says:

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. 🤪

Like

2. LiKao says:

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.

Like