Sleep Sort: Where Theory meets Sobering Reality
Tags: sleepsort, sortalgorithms, beginners, shell
Published: 2017-10-28 18:38:02

---
title: "Sleep Sort: Where Theory meets Sobering Reality"
published: true
description: How Sleep-Sort reminds us that sometimes the most important thing about computing is knowing its limitations.
tags: Sleep-Sort, sortalgorithms, beginners, Shell
cover_image: http://i.imgur.com/bPURIZn.png
---

Circa 6 years ago, an anonymous user posted on 4Chan:

![A screenshot of the original post on 4Chan](http://i.imgur.com/qe9tA16.png)

He outlined this amazing undiscovered sort written in Shell which, sure enough, worked. [Check out my repo to download the code and try it yourself!](https://github.com/SishaarRao/Sleep-Sort)

![A screenshot of me running the code](http://i.imgur.com/y4LHcSL.png)

I'll admit, I was bewildered at first. I could envision how this algorithm could be refined and implemented, whether it be cutting the time needed to output the value or scaling datasets accordingly. But then I thought to myself *if this sort (which off the top of my heads looks like an O(n) runtime) really works, then why hasn't some genius at IBM/Sun/Oracle implemented this already?* I couldn't be the first one wondering how to implement this. Why did people before me not go ahead with it? Why don't we use this in real life?

**Because at the end of the day, computers are still machines. At the end of the day, Theory is Theory, and Reality will always still be Reality**

##How/Why does Sleep-Sort Work?
The code for Sleep-Sort is as follows:

```Shell
#!/usr/bin/env bash

sort() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    sort "$1" &
    shift
done
wait
```

Let's dissect this part by part. (In case you were wondering, `#!/usr/bin/env bash` is called the [Shebang.](https://en.wikipedia.org/wiki/Shebang_(Unix)))

####The function
```Shell
sort() {
    sleep "$1"
    echo "$1"
}
```
This function is going to be called repeatedly by the code. It takes its first argument (denoted by `"$1"`) and sleeps for that amount of time. [Sleep](https://en.wikipedia.org/wiki/Sleep_(Unix)) is a command that pauses its current process (or more importantly its thread) for the given amount of seconds. For example, `sleep 100` would mean that the process "sleeps" or pauses for 100 seconds. 
It then calls [echo](https://en.wikipedia.org/wiki/Echo_(command)) on the first argument, which prints out the argument. Thus, the code `sort 3` would first sleep for `3` seconds and then print out `3`.

####The while-loop
```Shell
while [ -n "$1" ]
do
    sort "$1" &
    shift
done
wait
```
The while-loop's condition is `[ -n "$1" ]` As you can observe, we use the `-n` flag with the first argument. This flag returns true if the argument is nonzero. Thus, this loop will iterate until the argument at `$1` is null. 

We then call sort on the first argument `sort "$1"` The most important part of this, however, **is the ampersand (&) at the end** What this ampersand at the end does is begin the process described in the line, namely the sort function call, *in a different thread.* [Check this out for more info.](https://unix.stackexchange.com/questions/86247/what-does-ampersand-mean-at-the-end-of-a-shell-script-line)

On the next line, we call the built-in function shift. Since there are no parameters for the function, the default value to shift is 1. What shift does is it shifts the arguments we have over. The argument in `$2` goes to `$1`, the argument in `$3` goes to `$2` and so on. The original first argument is subsequently lost. 

####Running the code
![A sample run of the Sleep Sort](http://i.imgur.com/l7ixgTY.png)

As you now from the code above, we take the first argument and instantiate a separate thread that's sleeping for that argument length. Once it awakens, it prints out it's value. The 1 sleeps for 1 second, the 2 sleeps for 2 seconds, the 5 sleeps for 5, etc. Since the lower values sleep less, they print out their values earlier, and thus the list is now sorted. Isn't it amazing?

##Why Sleep-Sort Fails
Intuition told me that there's some fundamental flaw in this sort, and that for large datasets it breaks down. The success of sleep-sort relies on 3 fundamental assumptions, which often don't hold true as we go beyond a set of 5 or 10 numbers.

####1. The Processor can instantly determine which sub-process is the "least"
To generalize, the processor inherently possesses some data structure in which it stores sub-processes. It could be a [Tree](https://en.wikipedia.org/wiki/Tree_(data_structure)), a [Heap](https://en.wikipedia.org/wiki/Heap_(data_structure)), or some other data structure that allows the Processor to efficiently traverse its elements and find which one has the "least" value. By finding the least value, we mean finding **which process should be executed next**.

On the scale of milliseconds, sleep-sort can break down here. If we're given values 3 and 3.00001, the processor may determine the wrong process as the "least" value, simply because it takes the processor time, no matter how small, to find the correct process. 

####2. How Many Threads does the Computer Have?
Sleep-Sort depends on being able to separate each value into a different [thread](https://en.wikipedia.org/wiki/Thread_(computing)), and therefore it assumes that **for n elements, you subsequently have n available threads**. When you go into element sets of higher orders of magnitude, this assumption simply won't hold. Your computer has a finite amount of threads, and if you exceed that, then Sleep-Sort will fail.

####3. The Processor can rapidly switch between processes
Think of your processor as a miniscule ticker. When it executes multiple tasks in parallel, in reality our metaphorical ticker is rapidly switching back and forth between our tasks. It executes Task A for a millisecond, then Task B for a millisecond, and then back to Task A. It does this switching on such a small scale that, to the human eye, it seems that the two are running in parallel.

When you have a high number of tasks, this ticker begins to break down. As pointed in Issue #1, it struggles to determine which task to approach next, and it also may get bogged down by the task it is currently at. If it loses its efficiency to switch back and forth between tasks, Sleep-sort begins to break down as the tasks won't be perfectly executed in order.


##What does Sleep-Sort Teach Us
Scalability is an issue every software engineer has to keep in the back of their mind when they build a system. [Often, the best products are the ones who consider scalability from the very start.](https://groups.google.com/forum/#!msg/mi.jobs/poXLCW8udK4/_GHzqB9sG9gJ)

![Scalability leads to success](https://i.imgur.com/OMRk2CS.png)

What Sleep-Sort offered me, and what I hope it gave you, is a sobering reminder that what we believe works in a theoretical world may not work in a physical one. This statement seems obvious, but many create products that assume ideal situations and fail to account for scenarios where certain assumptions don't hold true. 

We need to take a step back and understand to the core how our system works. Furthermore, when we scale our solutions up for larger or different data sets, we need to understand how functionality is affected when we do so. The only way to gain this insight is to acknowledge the limitations of your environment, and the limitations of your machine.

**At the end of the day, your machine is still comprised of moving mechanical parts. Design your systems accordingly.**




I hope this article was helpful in understanding Sleep-Sort. [Check out my Sleep-Sort repo if you'd like to try/explore the sort for yourself](https://github.com/SishaarRao/Sleep-Sort/tree/master)! Above all, if you feel like I made any factual errors or if there's anything I can clarify/expand/modify to improve this post, please comment or reach out to me!