3 Most Slowest Sorting Algorithms
Tags: algorithms, python
Published: 2020-04-01 14:46:29

---
title: 3 Most Slowest Sorting Algorithms
published: true
date: 2020-03-30 15:52:00 UTC
tags: Algorithms,Python
canonical_url: https://coderscat.com/3-most-slow-sorting-algorithms
---

![smilie-495999_640.jpg](https://coderscat.com/wp-content/uploads/smilie-495999_640.jpg)

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.

```python
while not in_order(deck):
    shuffle(deck)
```

Let’s implement this algorithm in Python:

```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](https://en.wikipedia.org/wiki/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**.

![think-2853140_640.jpg](https://coderscat.com/wp-content/uploads/think-2853140_640.jpg)

Another variant is [Bozosort](http://www.cs.toronto.edu/~guerzhoy/180/lectures/W10/lec3/Bozosort.html), 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:

![sleep-sort.jpg](https://coderscat.com/wp-content/uploads/sleep-sort.jpg)

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:

```python
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](https://en.wikipedia.org/wiki/Slowsort) 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.

```python
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:

<iframe id="_ytid_91436" width="800" height="450" data-origwidth="800" data-origheight="450" src="https://www.youtube.com/embed/QbRoyhGdjnA?enablejsapi=1&amp;autoplay=0&amp;cc_load_policy=0&amp;iv_load_policy=1&amp;loop=0&amp;modestbranding=0&amp;rel=1&amp;fs=1&amp;playsinline=0&amp;autohide=2&amp;theme=dark&amp;color=red&amp;controls=1&amp;" class="__youtube_prefs__ no-lazyload" title="YouTube player" allow="autoplay; encrypted-media" allowfullscreen="" data-no-lazy="1" data-skipgform_ajax_framebjll="" style="box-sizing: border-box; margin: 0px; padding: 0px; border: 0px; max-width: 100%;"></iframe>
## Conclusion

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](https://coderscat.com/3-most-slow-sorting-algorithms) appeared first on [Coder's Cat](https://coderscat.com).