The life of coronavirus lockdown is weird, it is a life we have never experienced before.

Everything seems slow down, even shutdown.

As software engineers, we have always wanted to make our program run faster. On these unexperienced days, let us try to think about something from the opposite angle.

Do you know what is the slowest sorting algorithm?

Let’s have some fun and learn some unusual time complexity analysis.

Bogosort (a.k.a Monkey sort)

Bogosort is based on the generate and test paradigm.

while not in_order(deck):
    shuffle(deck)

Let’s implement this algorithm in Python:

import random
 
def bogosort(l):
    while not l == sorted(l):
        random.shuffle(l)
    return l
 
x = [3,2,4,7,3,6,9,1]
print bogosort(x)

Average time complexity is O((N-1)* N!), the best case occurs if the given array is already sorted.

You may think the worst-case needs infinite time.

It’s right in theory.

Actually, for any array with a fixed size, the expected running time of the algorithm is finite. This is because infinite monkey theorem holds in practice.

The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, such as the complete works of William Shakespeare.
– From Wikipedia

If we give enough time, bogosort sort will almost surely sort the array.

So, bogosort is also called Monkeysort.

Another variant is Bozosort, which only swap two elements until we get a sorted result. The runtime complexity of Bozosort is also O(N!).

Sleep sort

Could we sort an array without any comparison?

Yes, it’s possible!

Sleep sort is originally posted by anonymous user posted on 4Chan:

To implement it in Python, we spawning off one thread for each element of the array, and each thread wait for v seconds to start, where v is the value of an element:

from time import sleep
from threading import Timer

def sleep_sort(values):
    sleepsort.result = []
    def add1(x):
        sleepsort.result.append(x)
    mx = values[0]
    for v in values:
        if mx < v: mx = v
        Timer(v, add1, [v]).start()
    sleep(mx+1)
    return sleepsort.result

x = [3,2,4,7,3,6,9,1]
print sleep_sort(x)

#[1, 2, 3, 3, 4, 6, 7, 9]

The time complexity is O(Max(array)), very time consuming on performance!

Slow sort

Slow sort is a tongue-in-cheek joke of divide and conquer. It’s a recursive algorithm and seems similar to quicksort.

On the contrary, it’s extremely slow.

def slowsort(A, i, j):
    if i >= j:
        return
    m = (i+j) / 2
    slowsort(A, i, m)
    slowsort(A, m+1, j)
    if A[j] < A[m]:
        A[j], A[m] = A[m], A[j]
    slowsort(A, i, j-1)

x = [3,2,4,7,3,6,9,1]
slowsort(x, 0, len(x)-1)

Could you figure out the time complexity of this algorithm? Honestly, I can not :).

According to Wikipedia, even the best case is worse than Bubble sort.

This video is a visualization of how it works:

Conclusion

Although these sorting algorithms are actually not useful, they are interesting.

I hope you like it and have a smile. Stay well.