# An Algorithm that Sleeps to do Work

There are many sorting algorithms out there. But there are some special which makes them unique with their logic. Sleep Sorting Algorithm is such one. Kindly note that this may not have any real world implementation as the time complexity is very high for this.

### What is Sorting?

**Sorting** is a way of arranging a group of things in a specified order. Normally, the order is a “natural order.” Examples of natural orders are counting order or alphabetical order. In computing, time and memory usage are of concern when sorting. Some algorithms are very fast, but use a lot of memory, or vice versa. Usually, speed has higher priority. The speed of an algorithm is often determined by the number of compares and/or swaps required.

### Sleep Sort Algorithm:

The basic idea of sleep sort is to print the number *i*,after *i* seconds (or time units).

The pseudocode for sleep sort is:

procedure printNumber(n)

sleep n seconds

print n

end

for arg in args

run printNumber(arg) in background

end

wait for all processes to finish

For example, if the numbers to be sorted are 5, 3, 9:

Print 5 after 5 seconds;

Print 3 after 3 seconds; and

Print 9 after 9 seconds.

and woah, you realize that you get a sorted output!

### For Layman:

Let us try and understand sleep sort through an example. Assume that Ankit has 5 balloons. Each balloon has a number written on it, and each number belongs to the following set – {1,4,2,6,5}. Now, Ankit gives the balloons to 5 people, such that each person gets a single balloon. He instructs each person to “sleep” for ‘n’ number of seconds, where n is the number written on the respective person’s balloon, and tells the person to come and give him the balloon after he has finished “sleeping”. So, if a person receives a balloon with the number ‘4’ written on it, then he has to sleep for 4 seconds, and then give the balloon back to Ankit. So, in what order will Ankit receive the balloons? He will first receive the balloon with the number ‘1’ on it, then the one with ‘2’.. and so on. Thus, the order in which he will receive the balloons will be the sorted order.

### For Programmers:

Talking from a programmer’s perspective, for an array with elements a_{1, }a_{2…}a_{n }, threads th_{1,}th_{2….}th_{n} are created. A thread th_{i} is made to sleep for a_{i }seconds. When the thread th_{i}wakes up, a_{i }is printed. Therefore, in the end, all the numbers are printed in the sorted order.

### The Downside:

Though the practicality of sleep sort is a big question, it certainly is a very inventively thought algorithm. Suppose a guy enters two number 9999 and 1 to be sorted. 1 will be printed in a sec, whereas you have to wait 9999 secs to get 9999 to get printed. It takes total of 10000 secs to just sort two numbers.

### Implementation:

Here is Sample code in C

```
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main(int c, char **v)
{
while (--c > 1 && !fork());
sleep(c = atoi(v[c]));
printf("%d\n", c);
wait(0);
return 0;
}
```

Here is Sample code in Java(1.5+):

```
import java.util.concurrent.CountDownLatch;
public class SleepSort {
public static void sleepSortAndPrint(int[] nums) {
final CountDownLatch doneSignal = new CountDownLatch(nums.length);
for (final int num : nums) {
new Thread(new Runnable() {
public void run() {
doneSignal.countDown();
try {
doneSignal.await();
//using straight milliseconds produces unpredictable
//results with small numbers
//using 1000 here gives a nifty demonstration
Thread.sleep(num * 1000);
System.out.println(num);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
}
public static void main(String[] args) {
int[] nums = new int[args.length];
for (int i = 0; i < args.length; i++)
nums[i] = Integer.parseInt(args[i]);
sleepSortAndPrint(nums);
}
}
```

Click here for Source Code for Sleep Algorithm in Various languages

Click here to read more about sorting on wiki.

Here is list of various sorting algorithms out there:

- Bead sort
- Bogosort
- Bubble sort
- Circle Sort
- Cocktail sort
- Comb sort
- Counting sort
- Cycle sort
- Gnome sort
- Heapsort
- Insertion sort
- Merge sort
- Pancake sort
- Patience sort
- Permutation sort
- Quicksort
- Radix sort
- Selection sort
- Shell sort
- Sleep sort
- Stooge sort
- Strand sort
- Tree sort on a linked list

Hope you found this algorithm interesting. Let me know if you came across any such algorithms in comments.

## Recent Comments