Sleep Sort

Reading time: 35 minutes | Coding time: 5 minutes

Pseudo Code

for n in array
create a new thread and make it sleep for array[n] milliseconds
print array[n]
end
wait for all processes to finish

How it works

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 below implementations depict a simple demonstration of sleep sort in Java and C languages.

Implementations

• JAVA
• C

/**
 * @author Lakshmi
 */
class MyThread extends Thread
{
	int id ;
	Thread t;
	String s;
	MyThread(int id)
    {
		this.id = id;
		this.start();
	}
	public MyThread(String string) 
    {
		this.id = string.length();
		s = string;
		this.start();
	}
	public void run() 
    {
		try {
			Thread.sleep(id);
			if(s!= "")
				System.out.println(s);
			else
				System.out.println(id);
		} 
        catch (InterruptedException e) 
        {
			e.printStackTrace();
		}
	}
}
public class SleepSort 
{
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//int a[]= {9,8,7,6};
		//char a[] = {'c','v','a','d','b'};
		String a[] = {"abc","def","aa"};
		for(int i=0;i < a.length;i++) {
			new MyThread(a[i]);
		}
	}
}

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main()
{
    int a[] = {10,9,8,7,6};
        //int a[]= {9,8,7,6};
    //char a[] = {'c','v','a','d','b'};
        int c = sizeof(a) / sizeof(a[0]);
    while (--c >= 1 && !fork());
        sleep(c = a[c]);
    printf("%d\n", c);
    wait(0);
    return 0;
}

Complexity

The overall time complexity can be assumed as O(NlogN + max(input))

We can approximate the time complexity using the below reasoning-

• Creating multiple threads is done internally by the OS using a priority queue (used for scheduling purposes). Hence inserting all the array elements in the priority queue takes O(Nlog N) time.

• Also the output is obtained only when all the threads are processed, i.e., when all the elements ‘wakes’ up. Since it takes O(arr[i]) time to wake the ith array element’s thread. So it will take a maximum of O(max_element(array)) for the largest element of the array to wake up.

• Thus the overall time complexity can be assumed as O(NlogN + max_element(array)),
  where, N = number of elements in the input array, and array = input array elements

Drawbacks

• This algorithm won’t work for negative numbers as a thread cannot sleep for a negative amount of time.

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

• You many not get the correct output all the time because sometime is taken between scanning through each element as well as some other OS operations like inserting each threads in a priority queue for scheduling.

Improvements

• We have used the function sleep(arr[i]), which will make the thread sleep for arr[i] milliseconds which is a very small time period. By increasing sleep(arr[i]) to sleep(10arr[i]) or to generalize sleep(narr[i]) , the chances of producing the correct output is increased.
  But again,just like everything comes with a cost, this improvement will increase the runtime of the algorithm

Applications

This sorting algorithm may not have any real world application as it is not efficient when the array has very larger values stored in it.