Sorting algorithms/Sleep sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 04:56, 3 February 2015

In general, sleep sort works by starting a separate task for each item to be sorted, where each task sleeps for an interval corresponding to the item's sort key, then emits the item. Items are then collected sequentially in time.

Task: Write a program that implements sleep sort. Have it accept non-negative integers on the command line and print the integers in sorted order. If this is not idomatic in your language or environment, input and output may be done differently. Enhancements for optimization, generalization, practicality, robustness, and so on are not required.

Sleep sort was presented anonymously on 4chan and has been discussed on Hacker News.

Ada

<lang Ada>with Ada.Text_IO; with Ada.Command_Line; use Ada.Command_Line; procedure SleepSort is

  task type PrintTask (num : Integer);
  task body PrintTask is begin
     delay Duration (num) / 100.0;
     Ada.Text_IO.Put(num'Img);
  end PrintTask;
  type TaskAcc is access PrintTask;
  TaskList : array (1 .. Argument_Count) of TaskAcc;

begin

  for i in TaskList'Range loop
     TaskList(i) := new PrintTask(Integer'Value(Argument(i)));
  end loop;

end SleepSort;</lang>

Output:

./sleepsort 35 21 11 1 2 27 32 7 42 20 50 42 25 41 43 14 46 20 30 8
 1 2 7 8 11 14 20 20 21 25 27 30 32 35 41 42 42 43 46 50

APL

<lang APL> sleepsort←{{r}⎕TSYNC{r,←⊃⍵,⎕DL ⍵}&¨⍵,r←⍬} </lang>

BBC BASIC

Works with: BBC BASIC for Windows

This does not explicitly 'sleep', but uses timers to implement the different delays. <lang bbcbasic> INSTALL @lib$+"TIMERLIB"

     DIM test%(9)
     test%() = 4, 65, 2, 31, 0, 99, 2, 83, 782, 1
     
     FOR i% = 0 TO DIM(test%(),1)
       p% = EVAL("!^PROCtask" + STR$(i%))
       tid% = FN_ontimer(100 + test%(i%), p%, 0)
     NEXT
     
     REPEAT
       WAIT 0
     UNTIL FALSE
     
     DEF PROCtask0 : PRINT test%(0) : ENDPROC
     DEF PROCtask1 : PRINT test%(1) : ENDPROC
     DEF PROCtask2 : PRINT test%(2) : ENDPROC
     DEF PROCtask3 : PRINT test%(3) : ENDPROC
     DEF PROCtask4 : PRINT test%(4) : ENDPROC
     DEF PROCtask5 : PRINT test%(5) : ENDPROC
     DEF PROCtask6 : PRINT test%(6) : ENDPROC
     DEF PROCtask7 : PRINT test%(7) : ENDPROC
     DEF PROCtask8 : PRINT test%(8) : ENDPROC
     DEF PROCtask9 : PRINT test%(9) : ENDPROC</lang>

Output:

Brainf***

<lang C> >>>>>,----------[++++++++ ++[->+>+<<]>+>[-<<+>>]+++ +++++[-<------>]>>+>,----

<<+[->>>>>+<<<<<]>>

]>>>[<<<<[<<<[->>+<<[->+> [-]<<]]>[-<+>]>[-<<<.>>>> ->>>>>[>>>>>]<-<<<<[<<<<< ]+<]<<<<]>>>>>[>>>>>]<] </lang> Not exactly 'sleep' sort but it is similar, it inputs an array and in each iteration reduces elements by 1 and prints the number if result is 0.

Input: 1539\n

Output: 1359

C

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

}</lang> Running it:<lang>% ./a.out 5 1 3 2 11 6 4 1 2 3 4 5 6 11</lang> If you worry about time efficiency of this sorting algorithm (ha!), you can make it a 100 times faster by replacing the sleep(... with usleep(10000 * (c = atoi(v[c]))). The smaller the coefficient, the faster it is, but make sure it's not comparable to your kernel clock ticks or the wake up sequence will be wrong.

C++

Works with: C++11

include <iostream>
include <thread>
include <vector>
include <unistd.h>

using namespace std;

void sortThread( int x ) {

   usleep( 10000 * x );
   cout << x << " ";

}

int main() {

   vector<thread*> threads;

   srand( ( unsigned )time( NULL ) );

   cout << "unsorted:" << endl;
   for( int x = 0; x < 15; x++ )
   {
       int r = rand() % 20 + 5;
       cout << r << " ";
       thread* t = new thread( sortThread, r );
       threads.push_back( t );
   }
   cout << endl << endl << "sorted:" << endl;

   for( vector<thread*>::iterator t = threads.begin(); t != threads.end(); t++ )
   {
       ( *t )->join();
       delete ( *t );
   }

   cout << endl << endl;
   return 0;

} </lang>

Output:

unsorted:
8 15 14 9 17 20 16 24 6 24 21 23 19 23 19 

sorted:
6 8 9 14 15 16 17 19 19 20 21 23 23 24 24

C#

<lang csharp>using System; using System.Collections.Generic; using System.Linq; using System.Threading;

class Program {

   static void ThreadStart(object item)
   {
       Thread.Sleep(1000 * (int)item);
       Console.WriteLine(item);
   }

   static void SleepSort(IEnumerable<int> items)
   {
       foreach (var item in items)
       {
           new Thread(ThreadStart).Start(item);
       }
   }

   static void Main(string[] arguments)
   {
       SleepSort(arguments.Select(int.Parse));
   }

}</lang>

Clojure

Using core.async <lang clojure>(ns sleepsort.core

 (require [clojure.core.async :as async :refer [chan go <! <!! >! timeout]]))

(defn sleep-sort [l]

 (let [c (chan (count l))]
   (doseq [i l]
     (go (<! (timeout (* 1000 i)))
         (>! c i)))
   (<!! (async/into [] (async/take (count l) c)))))</lang>

<lang clojure>(sleep-sort [4 5 3 1 2 7 6])

=> [1 2 3 4 5 6 7]</lang>

CoffeeScript

Works with: node.js

<lang coffeescript> after = (s, f) -> setTimeout f, s*1000

Setting Computer Science back at least a century, maybe more,
this algorithm sorts integers using a highly parallelized algorithm.

sleep_sort = (arr) ->

 for n in arr
   do (n) -> after n, -> console.log n

do ->

 input = (parseInt(arg) for arg in process.argv[2...])
 sleep_sort input

</lang> output <lang> > time coffee sleep_sort.coffee 5, 1, 3, 4, 2 1 2 3 4 5

real 0m5.184s user 0m0.147s sys 0m0.024s </lang>

Common Lisp

Works with: SBCL

<lang lisp>(defun sleeprint(n)

   (sleep (/ n 10))
   (format t "~a~%" n))

(loop for arg in (cdr sb-ext:*posix-argv*) doing

     (sb-thread:make-thread (lambda() (sleeprint (parse-integer arg)))))

(loop while (not (null (cdr (sb-thread:list-all-threads)))))</lang>

Output:

$ sbcl --script ss.cl 3 1 4 1 5
1
1
3
4
5

D

<lang d>import std.stdio, std.conv, std.datetime, std.array, core.thread;

final class SleepSorter: Thread {

   private immutable uint val;

   this(in uint n) /*pure nothrow @safe*/ {
       super(&run);
       val = n;
   }

   private void run() {
       Thread.sleep(dur!"msecs"(1000 * val));
       writef("%d ", val);
   }

}

void main(in string[] args) {

   if (!args.empty)
       foreach (const arg; args[1 .. $])
           new SleepSorter(arg.to!uint).start;

}</lang>

Output:

sorting_algorithms_sleep_sort 1 6 2 5 3 4
1 2 3 4 5 6

Dart

<lang dart>import 'dart:async';

Future<List<int>> sleepsort(List<int> input) {

 List<Future<int>> tasks = [];
 List<int> result = [];
 for (int i in input) {
   tasks.add(new Future.delayed(new Duration(seconds: i), () {
     result.add(i);
   }));
 }
 return Future.wait(tasks).then((_) {
   return result;
 });

}

sleepsort.sleepsort([3, 1, 2]).then((List<int> sorted) {

 print(sorted);

}); </lang>

Output:

1 2 3

Delphi

<lang Delphi>program SleepSortDemo;

{$APPTYPE CONSOLE}

uses

 Windows, SysUtils, Classes;

type

 TSleepThread = class(TThread)
 private
   FValue: Integer;
   FLock: PRTLCriticalSection;
 protected
   constructor Create(AValue: Integer; ALock: PRTLCriticalSection);
   procedure Execute; override;
 end;

constructor TSleepThread.Create(AValue: Integer; ALock: PRTLCriticalSection); begin

 FValue:= AValue;
 FLock:= ALock;
 inherited Create(False);

end;

procedure TSleepThread.Execute; begin

 Sleep(1000 * FValue);
 EnterCriticalSection(FLock^);
 Write(FValue:3);
 LeaveCriticalSection(FLock^);

end;

var

 A: array[0..15] of Integer;
 Handles: array[0..15] of THandle;
 Threads: array[0..15] of TThread;
 Lock: TRTLCriticalSection;
 I: Integer;

begin

 for I:= Low(A) to High(A) do
   A[I]:= Random(15);
 for I:= Low(A) to High(A) do
   Write(A[I]:3);
 Writeln;

 InitializeCriticalSection(Lock);
 for I:= Low(A) to High(A) do begin
   Threads[I]:= TSleepThread.Create(A[I], @Lock);
   Handles[I]:= Threads[I].Handle;
 end;
 WaitForMultipleObjects(Length(A), @Handles, True, INFINITE);
 for I:= Low(A) to High(A) do
   Threads[I].Free;
 DeleteCriticalSection(Lock);

 Writeln;
 ReadLn;

end.</lang> Output:

  0  0 12  3  4 10  4  2  5  6  1  7  1 12  0  4
  0  0  0  1  1  2  3  4  4  4  5  6  7 10 12 12

Erlang

<lang erlang>#!/usr/bin/env escript %% -*- erlang -*- %%! -smp enable -sname sleepsort

main(Args) ->

   lists:foreach(fun(Arg) ->
                         timer:send_after(5 * list_to_integer(Arg), self(), Arg)
                 end, Args),
   loop(length(Args)).

loop(0) ->

ok;

loop(N) ->

   receive
       Num ->
           io:format("~s~n", [Num]),
           loop(N - 1)
   end.</lang>

Output:

./sleepsort 2 4 8 12 35 2 12 1
1
2
2
4
8
12
12
35

Euphoria

<lang euphoria>include get.e

integer count

procedure sleeper(integer key)

   ? key
   count -= 1

end procedure

sequence s, val atom task

s = command_line() s = s[3..$] if length(s)=0 then

   puts(1,"Nothing to sort.\n")

else

   count = 0
   for i = 1 to length(s) do
       val = value(s[i])
       if val[1] = GET_SUCCESS then
           task = task_create(routine_id("sleeper"),{val[2]})
           task_schedule(task,{val[2],val[2]}/10)
           count += 1
       end if
   end for
   
   while count do
       task_yield()
   end while

end if</lang>

Go

<lang go>package main

import ( "fmt" "log" "os" "strconv" "time" )

func main() { out := make(chan uint64) for _, a := range os.Args[1:] { i, err := strconv.ParseUint(a, 10, 64) if err != nil { log.Fatal(err) } go func(n uint64) { time.Sleep(time.Duration(n) * time.Millisecond) out <- n }(i) } for _ = range os.Args[1:] { fmt.Println(<-out) } }</lang> Usage and output:

./sleepsort 3 1 4 1 5 9
1
1
3
4
5
9

Groovy

<lang groovy> @Grab(group = 'org.codehaus.gpars', module = 'gpars', version = '1.2.1') import groovyx.gpars.GParsPool

GParsPool.withPool args.size(), {

   args.eachParallel {
       sleep(it.toInteger() * 10)
       println it
   }

} </lang>

Sample Run:

> groovy sleepsort.groovy 42 23 16 15 8 4
4
8
15
16
23
42

Haskell

<lang haskell>import System.Environment import Control.Concurrent import Control.Monad

sleepSort :: [Int] -> IO () sleepSort values = do chan <- newChan forM_ values (\time -> forkIO (threadDelay (50000 * time) >> writeChan chan time)) forM_ values (const (readChan chan >>= print))

main :: IO () main = getArgs >>= sleepSort . map read</lang>

Icon and Unicon

The following solution only works in Unicon.

<lang unicon>procedure main(A)

   every insert(t:=set(),mkThread(t,!A))
   every spawn(!t)    # start threads as closely grouped as possible
   while (*t > 0) do write(<<@)

end

procedure mkThread(t,n) # 10ms delay scale factor

   return create (delay(n*10),delete(t,&current),n@>&main)

end</lang>

Sample run:

->ss 3 1 4 1 5 9 2 6
1
1
2
3
4
5
6
9
->

Java

Works with: Java version 1.5+

<lang java5>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); } }</lang> Output (using "3 1 4 5 2 3 1 6 1 3 2 5 4 6" as arguments):

JavaScript

<lang javascript>Array.prototype.timeoutSort = function (f) { this.forEach(function (n) { setTimeout(function () { f(n) }, 5 * n) }); } </lang> Usage and output: <lang javascript>[1, 9, 8, 7, 6, 5, 3, 4, 5, 2, 0].timeoutSort(function(n) { document.write(n + 'br'); })</lang>

Lua

Here's a slow implementation using only stock C Lua:

<lang lua>function sleeprint(n)

 local t0 = os.time()
 while os.time() - t0 <= n do
   coroutine.yield(false)
 end
 print(n)
 return true

end

coroutines = {} for i=1, #arg do

 wrapped = coroutine.wrap(sleeprint)
 table.insert(coroutines, wrapped)
 wrapped(tonumber(arg[i]))

end

done = false while not done do

 done = true
 for i=#coroutines,1,-1 do
   if coroutines[i]() then
     table.remove(coroutines, i)
   else
     done = false
   end
 end

end</lang>

By installing LuaSocket, you can get better than 1-second precision on the clock, and therefore faster output:

<lang lua>socket = require 'socket'

function sleeprint(n)

 local t0 = socket.gettime()
 while (socket.gettime() - t0)*100 <= n do
   coroutine.yield(false)
 end
 print(n)
 return true

end

coroutines = {} for i=1, #arg do

 wrapped = coroutine.wrap(sleeprint)
 table.insert(coroutines, wrapped)
 wrapped(tonumber(arg[i]))

end

done = false while not done do

 done = true
 for i=#coroutines,1,-1 do 
   if coroutines[i]() then
     table.remove(coroutines, i)
   else
     done = false
   end
 end

end</lang>

Either way, the output is the same:

Output:

$ lua sleep_sort.lua 3 1 4 1 5 9 2 6 5 3 5
1
1
2
3
3
4
5
5
5
6
9

Mathematica

<lang mathematica>SleepSort = RunScheduledTask[Print@#, {#, 1}] & /@ # &; SleepSort@{1, 9, 8, 7, 6, 5, 3, 4, 5, 2, 0};</lang>

Output:

NetRexx

As implemented this sample goes beyond the scope of the task as defined; it will handle negative numbers.

<lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary import java.util.concurrent.CountDownLatch

-- ============================================================================= class RSortingSleepsort

 properties constant private
   dflt = '-6 3 1 4 5 2 3 -7 1 6 001 3 -9 2 5 -009 -8 4 6 1 9 8 7 6 5 -7 3 4 5 2 0 -2 -1 -5 -4 -3 -0 000 0'
 properties indirect
   startLatch = CountDownLatch
   doneLatch  = CountDownLatch
   floor      = 0
   sorted     = 
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 method main(args = String[]) public static
   arg = Rexx(args)
   if arg =  then arg = dflt
   say ' unsorted:' arg
   say '   sorted:' (RSortingSleepsort()).sleepSort(arg)
   return
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 method sleepSort(iArg) public
   setStartLatch(CountDownLatch(1))           -- used to put all threads on hold until we're ready to run
   setDoneLatch(CountDownLatch(iArg.words())) -- used to indicate all work is done
   loop mn = 1 to iArg.words()
     setFloor(getFloor().min(iArg.word(mn)))   -- save smallest -ve number so we can use it as a scale for sleep
     Thread(SortThread(iArg.word(mn))).start() -- loop through input and create a thread for each element
     end mn
   getStartLatch().countDown() -- cry 'Havoc', and let slip the dogs of war.
   do
     getDoneLatch().await() -- wait for worker threads to complete
   catch ix = InterruptedException
     ix.printStackTrace()
   end
   return getSorted()

-- ============================================================================= class RSortingSleepsort.SortThread dependent implements Runnable

 properties indirect
   num
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 method SortThread(nm)
   setNum(nm)
   return
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 method run() public
   do
     parent.getStartLatch().await()                 -- wait until all threads are constructed
     sleepTime = getNum() + parent.getFloor().abs() -- shifted by value of smallest number (permits numbers < 0)
     sleepTime = sleepTime * 250                    -- scale up; milliseconds are not granular enough
     Thread.sleep(sleepTime)                        -- wait for this number's turn to run
   catch ie = InterruptedException
     ie.printStackTrace()
   end
   do protect parent -- lock the parent to prevent collisions
     parent.setSorted((parent.getSorted() num).strip()) -- stow the number in the results List
   end
   parent.getDoneLatch().countDown() -- this one's done; decrement the latch
   return

</lang> Output:

 unsorted: -6 3 1 4 5 2 3 -7 1 6 001 3 -9 2 5 -009 -8 4 6 1 9 8 7 6 5 -7 3 4 5 2 0 -2 -1 -5 -4 -3 -0 000 0
   sorted: -9 -009 -8 -7 -7 -6 -5 -4 -3 -2 -1 000 0 0 -0 1 1 001 1 2 2 2 3 3 3 3 4 4 4 5 5 5 5 6 6 6 7 8 9

Nim

Translation of: C

<lang nim>import os, posix, strutils

var c = paramCount() + 1 while true:

 dec c
 if c <= 1: break
 if fork() == 0: break

let i = parseInt paramStr c sleep i echo i var pid: cint = 0 discard wait(pid)</lang> Usage:

$ ./sleepsort 5 1 3 2 11 6 4
1
2
3
4
5
6
11

Objeck

<lang objeck> use System.Concurrency; use Collection;

bundle Default {

 class Item from Thread {
   @value : Int;
   
   New(value : Int) {
     Parent();
     @value := value;
   }

   method : public : Run(param : System.Base) ~ Nil {
     Sleep(1000 * @value);
     @value->PrintLine();
   }
 }

 class SleepSort {
   function : Main(args : String[]) ~ Nil {
     items := Vector->New();
     each(i : args) {
       items->AddBack(Item->New(args[i]->ToInt()));
     };
   
     each(i : items) {
       items->Get(i)->As(Item)->Execute(Nil);
     };
   }
 }

} </lang>

Objective-C

<lang objc>#import <Foundation/Foundation.h>

int main(int argc, char **argv) {

   NSOperationQueue *queue = [[NSOperationQueue alloc] init];
   while (--argc) {
       int i = atoi(argv[argc]);
       [queue addOperationWithBlock: ^{
           sleep(i);
           NSLog(@"%d\n", i);
       }];
   }
   [queue waitUntilAllOperationsAreFinished];

}</lang> Rather than having multiple operations that sleep, we could also dispatch the tasks after a delay: <lang objc>#import <Foundation/Foundation.h>

int main(int argc, char **argv) {

   while (--argc) {
       int i = atoi(argv[argc]);
       dispatch_after(dispatch_time(DISPATCH_TIME_NOW, i * NSEC_PER_SEC),
                      dispatch_get_main_queue(),
                      ^{ NSLog(@"%d\n", i); });
   }

}</lang>

Oforth

Instead of printing numbers, each task sends its integer into a channel (after sleeping 20 * n milliseconds). This allows the main task to create a new sorted list with those integers.

20 milliseconds is used to (try to) handle scheduler tick on Windows systems (around 15 ms). On Linux systems (after kernel 2.6.8), this value can be smaller.

<lang Oforth>func: sleepSort(l) { | ch n |

  Channel new ->ch
  l forEach: n [ #[ System sleep(n 20 *) ch send(n) ] & ]
  ListBuffer newSize(l size) #[ ch receive over add ] times(l size)

}</lang>

Output:

sleepSort(100 seq 100 seq +) println
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14,
 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 2
5, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36,
 37, 37, 38, 38, 39, 39, 40, 40, 41, 41, 42, 42, 43, 43, 44, 44, 45, 45, 46, 46, 47, 47, 4
8, 48, 49, 49, 50, 50, 51, 51, 52, 52, 53, 53, 54, 54, 55, 55, 56, 56, 57, 57, 58, 58, 59,
 59, 60, 60, 61, 61, 62, 62, 63, 63, 64, 64, 65, 65, 66, 66, 67, 67, 68, 68, 69, 69, 70, 7
0, 71, 71, 72, 72, 73, 73, 74, 74, 75, 75, 76, 76, 77, 77, 78, 78, 79, 79, 80, 80, 81, 81,
 82, 82, 83, 83, 84, 84, 85, 85, 86, 86, 87, 87, 88, 88, 89, 89, 90, 90, 91, 91, 92, 92, 9
3, 93, 94, 94, 95, 95, 96, 96, 97, 97, 98, 98, 99, 99, 100, 100]

Perl

Basically the C code. <lang Perl>1 while ($_ = shift and @ARGV and !fork); sleep $_; print "$_\n"; wait;</lang>

A more optimal solution makes use of Coro, a cooperative threading library. It has the added effect of being much faster, fully deterministic (sleep is not exact), and it allows you to easily collect the return value: <lang Perl>use Coro; $ret = Coro::Channel->new; @nums = qw(1 32 2 59 2 39 43 15 8 9 12 9 11);

for my $n (@nums){ async { Coro::cede for 1..$n; $ret->put($n); } }

print $ret->get,"\n" for 1..@nums;</lang>

Perl 6

<lang Perl6>await map -> $delay { start { sleep $delay ; say $delay } },

   <6 8 1 12 2 14 5 2 1 0>;</lang>

Output:

PicoLisp

Sleeping in main process

<lang PicoLisp>(de sleepSort (Lst)

  (make
     (for (I . N) Lst
        (task (- I) (* N 100)  N N  I I
           (link N)
           (pop 'Lst)
           (task (- I)) ) )
     (wait NIL (not Lst)) ) )</lang>

Sleeping in child processes

<lang PicoLisp>(de sleepSort (Lst)

  (make
     (for N Lst
        (task (pipe (wait (* N 100))) N N
           (link N)
           (pop 'Lst)
           (task (close @)) ) )
     (wait NIL (not Lst)) ) )</lang>

Output in both cases:

: (sleepSort (3 1 4 1 5 9 2 6 5))
-> (1 1 2 3 4 5 5 6 9)

Just printing (no sorted result list)

Basically the C code. <lang PicoLisp>(for N (3 1 4 1 5 9 2 6 5)

  (unless (fork)
     (call 'sleep N)
     (msg N)
     (bye) ) )</lang>

Output:

Prolog

Works with SWI-Prolog. <lang Prolog>sleep_sort(L) :- thread_pool_create(rosetta, 1024, []) , maplist(initsort, L, LID), maplist(thread_join, LID, _LStatus), thread_pool_destroy(rosetta).

initsort(V, Id) :- thread_create_in_pool(rosetta, (sleep(V), writeln(V)), Id, []).

</lang> Output :

 sleep_sort([5, 1, 3, 2, 11, 6, 3, 4]).
1
2
3
3
4
5
6
11
true.

PureBasic

<lang PureBasic>NewMap threads()

Procedure Foo(n)

 Delay(n)
 PrintN(Str(n))

EndProcedure

If OpenConsole()

 For i=1 To CountProgramParameters()
   threads(Str(i)) = CreateThread(@Foo(), Val(ProgramParameter()))
 Next
 
 ForEach threads()
   WaitThread(threads())
 Next
 Print("Press ENTER to exit"): Input()

EndIf</lang>

Sleep_sort.exe 3 1 4 1 5 9
1
1
3
4
5
9
Press ENTER to exit

Python

<lang python>from time import sleep from threading import Timer

def sleepsort(values):

   sleepsort.result = []
   def add1(x):
       sleepsort.result.append(x)
   mx = values[0]
   for v in values:
       if mx < v: mx = v
       Timer(v, add1, [v]).start()
   sleep(mx+1)
   return sleepsort.result

if __name__ == '__main__':

   x = [3,2,4,7,3,6,9,1]
   if sleepsort(x) == sorted(x):
       print('sleep sort worked for:',x)
   else:
       print('sleep sort FAILED for:',x)</lang>

Sample output

sleep sort worked for: [3, 2, 4, 7, 3, 6, 9, 1]

Racket

lang racket

accepts a list to sort

(define (sleep-sort lst)

 (define done (make-channel))
 (for ([elem lst])
   (thread 
    (λ () 
      (sleep elem)
      (channel-put done elem))))
 (for/list ([_ (length lst)])
   (channel-get done)))

outputs '(2 5 5 7 8 9 10)

(sleep-sort '(5 8 2 7 9 10 5)) </lang>

REXX

This sort will accept any manner of numbers, or for that matter, any character string as well.
REXX isn't particular what is being sorted.

This REXX version only works with Regina REXX (as the program uses the fork func tion.
REXX isn't particular what is being sorted. <lang rexx>/*REXX program implements a sleep sort (with numbers entered from C.L.).*/ numeric digits 300 /*over the top, but what the hey!*/

                                      /*  (above)  ··· from vaudeville.*/

.= /*placeholder for the array of #s*/

stuff= 1e9 50 5 40 4 1 100 30 3 12 2 8 9 7 6 6 10 20 0 /*alphabetically*/ parse arg numbers /*let the user specify on the CL.*/ if numbers= then numbers=stuff /*Not specified? Then use default*/ N=words(numbers) /*N is the number of numbers. */ w=length(N) /*width of N (for nice output).*/ say N 'numbers to be sorted:' numbers /*informative informational info.*/

   do j=1  for N                      /*let's start to boogie-woogie.  */
   #.j=word(numbers,j)                /*plug in one number at a time.  */
   if datatype(#.j,'N')  then #.j=#.j/1     /*normalize it if a number.*/
   call fork                          /*only REGINA REXX supports FORK.*/
   call sortItem j                    /*start a sort for array number. */
   end   /*j*/

     do forever  while \inOrder(N)    /*wait for the sorts to complete.*/
     call sleep 1                     /*1 sec is minimum effective time*/
     end    /*forever while*/         /*well, other than zero seconds. */

m=max(length(#.1),length(#.N)) /*width of smallest | largest num*/ say; say 'after sort:' /*display blank line and a title.*/

     do k=1  for N                    /*list (sorted) array's elements.*/
     say left(,20)  'array element'  right(k,w)   '───►'   right(#.k,m)
     end   /*k*/

exit /*stick a fork in it, we're done.*/ /*───────────────────────────────────SortItem subroutine────────────────*/ sortItem: procedure expose #.; parse arg ? /*sorts single item.*/

             do Asort=1  until \switched           /*cook until cooked.*/
             switched=0                            /*hunky-dorey so far*/
                           do i=1   while   #.i\==  &  \switched
                           if #.? >= #.i then iterate     /*this one ok*/
                           parse value   #.?  #.i     with     #.i  #.?
                           switched=1              /* [↑]  swapped one.*/
                           end   /*i*/
             if Asort//?==0  then call sleep switched   /*sleep if last*/
             end   /*Asort*/

return /*Sleeping Beauty awakes. Not to worry: (c) = circa 1697.*/ /*───────────────────────────────────InOrder subroutine─────────────────*/ inOrder: procedure expose #.; parse arg howMany /*is array in order? */

         do m=1  for howMany-1;   next=m+1;  if #.m>#.next  then return 0
         end   /*m*/                 /*keep looking for fountain of yut*/

return 1 /*yes, indicate with an indicator.*/ </lang> output when using the default input

19 numbers to be sorted: 1e9 50 5 40 4 1 100 30 3 12 2 8 9 7 6 6 10 20 0

after sort:
                     array element  1 ───>          0
                     array element  2 ───>          1
                     array element  3 ───>          2
                     array element  4 ───>          3
                     array element  5 ───>          4
                     array element  6 ───>          5
                     array element  7 ───>          6
                     array element  8 ───>          6
                     array element  9 ───>          7
                     array element 10 ───>          8
                     array element 11 ───>          9
                     array element 12 ───>         10
                     array element 13 ───>         12
                     array element 14 ───>         20
                     array element 15 ───>         30
                     array element 16 ───>         40
                     array element 17 ───>         50
                     array element 18 ───>        100
                     array element 19 ───> 1000000000

Ruby

<lang ruby>require 'thread'

nums = ARGV.collect(&:to_i) sorted = [] mutex = Mutex.new

threads = nums.collect do |n|

 Thread.new do
   sleep 0.01 * n
   mutex.synchronize {sorted << n}
 end

end threads.each {|t| t.join}

p sorted</lang>

Example

$ ruby sleepsort.rb 3 1 4 5 2 3 1 6 1 3 2 5 4 6
[1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6]

Rust

<lang rust>// rust 0.9

fn main() {

   let args = std::os::args();
   for arg in args.tail().iter()
   {
       let n = from_str::<u64>(*arg).unwrap();
       do std::task::spawn
       {
           std::io::timer::sleep(n);
           println!("{}", n);
       }
   }

}</lang>

Scala

<lang scala>object SleepSort {

 def sort(nums:Seq[Int])=nums foreach {n =>
   scala.concurrent.ops.spawn{
     Thread.sleep(500*n)
     print(n+" ")
   }
 }

 def main(args:Array[String])={
   sort(args map (_.toInt))
 }

}</lang> Example:

> scala SleepSort 1 9 8 7 6 5 3 4 5 2 0
0 1 2 3 4 5 5 6 7 8 9

Swift

<lang Swift>import Foundation

for i in [5, 2, 4, 6, 1, 7, 20, 14] {

   let time = dispatch_time(DISPATCH_TIME_NOW,
       Int64(i * Int(NSEC_PER_SEC)))
   
   dispatch_after(time, dispatch_get_main_queue()) {
       println(i)
   }

}

CFRunLoopRun()</lang>

Output:

Sidef

<lang ruby>ARGV.map{.to_i}.map{ |i|

   {Sys.sleep(i); say i}.fork;

}.each{.wait};</lang>

Output:

% sidef test.sf 5 1 3 2 11 6 4
1
2
3
4
5
6
11

Tcl

<lang tcl>#!/bin/env tclsh set count 0 proc process val {

   puts $val
   incr ::count

}

Schedule the output of the values

foreach val $argv {

   after [expr {$val * 10}] [list process $val]

}

Run event loop until all values output...

while {$count < $argc} {

   vwait count

}</lang> Demonstrating:

bash$ sleepsort.tcl 3 1 4 5 2 3 1 6 1 3 2 5 4 6
1
1
1
2
2
3
3
3
4
4
5
5
6
6

UNIX Shell

Works with: Bourne Shell

<lang bash>f() {

   sleep "$1"
   echo "$1"

} while [ -n "$1" ] do

   f "$1" &
   shift

done wait</lang> Usage and output:

sh sleepsort.sh 3 1 4 1 5 9
1
1
3
4
5
9