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 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

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) {
			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:

1. Bead sort
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
17. Radix sort
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.