Algorithms Computer Science

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)

threads = []
for i in items:
  thread = threading.Thread(target=sleep_sort, args=(i,))
  threads.append(thread)
  thread.start()

for t in threads:
  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 comments on “Unconventional Sorting Algorithms

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: