# Sleep Sort Algorithm: The 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 a1, a2…an , threads th1,th2….thn are created. A thread thi is made to sleep for ai seconds. When the thread thi wakes up, ai 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

 Source code
```#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+):

 Source code
```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) {
public void run() {
doneSignal.countDown();
try {
doneSignal.await();

//using straight milliseconds produces unpredictable
//results with small numbers
//using 1000 here gives a nifty demonstration
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);
}
}```

Here is list of various sorting algorithms out there:

2. Bogosort
3. Bubble sort
4. Circle Sort
5. Cocktail sort
6. Comb sort
7. Counting sort
8. Cycle sort
9. Gnome sort
10. Heapsort
11. Insertion sort
12. Merge sort
13. Pancake sort
14. Patience sort
15. Permutation sort
16. Quicksort
18. Selection sort
19. Shell sort
20. Sleep sort
21. Stooge sort
22. Strand sort
23. Tree sort on a linked list

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

Pravin Hanchinal

Pravin Hanchinal is a Professional Speaker, Educator, Edupreneur, Entrepreneur,Big Data,IoT and Cloud Evangelist.Trained around 7500+ people which include teachers, students, industry on recent technologies. Though passionate about being a technical coach, educator but his hunger for learning never stops. Long way ahead, yet to accomplish a lot for this proud son of a agriculturist. He is available for conducting workshop for students, faculty, industry and general audiences. In Nutshell: Sapiosexual, Edupreneur, FOSS, Cloud and Big Data Evangelist

### 1 Response

1. June 11, 2018

[…] Source code […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.