DEV Community


Posted on • Originally published at on

3 Most Slowest Sorting Algorithms


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):
Enter fullscreen mode Exit fullscreen mode

Let’s implement this algorithm in Python:

import random

def bogosort(l):
    while not l == sorted(l):
    return l

x = [3,2,4,7,3,6,9,1]
print bogosort(x)
Enter fullscreen mode Exit fullscreen mode

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):
    mx = values[0]
    for v in values:
        if mx < v: mx = v
        Timer(v, add1, [v]).start()
    return sleepsort.result

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

#[1, 2, 3, 3, 4, 6, 7, 9]
Enter fullscreen mode Exit fullscreen mode

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:
    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)
Enter fullscreen mode Exit fullscreen mode

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:


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

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

The post 3 Most Slow Sorting Algorithms appeared first on Coder's Cat.

Top comments (0)