# Implement Sleep Sort

Sleep Sort is an integer sorting algorithm I found on the Internet. It opens an output stream, and for each input numbers in parallel, delay for the number seconds and output that number. Because of the delays, the highest number will be outputted last. I estimate it has O(n + m), where n is the number of elements and m is the highest number.

Here is the original code in Bash

#!/bin/bash
function f() {
sleep "$1" echo "$1"
}
while [ -n "$1" ] do f "$1" &
shift
done
wait


Here is the pseudocode

sleepsort(xs)
output = []
fork
for parallel x in xs:
sleep for x seconds
append x to output
wait until length(output) == length(xs)
return output


Your task is to implement Sleep Sort as a function in the programming language of your choice. You can neglect any concurrency factors such as race conditions and never lock any shared resources. The shortest code wins. The function definition counts toward the code length.

The input list is limited to non-negative integers only, and the length of the input list is expected to reasonably long (test at least 10 numbers) so race conditions never happen. and assuming race conditions never happen.

• What counts towards the length? Complete programs including IO or just the relevant routine? Jun 2, 2011 at 10:21
• A problem with this. Depending on the order of the list, you might not read the entire list before the first value is printed. For example, a large list that takes 45 seconds to read, the first value is 2 and the last value is 1. The thread to print 1 might be executed after the 2 is printed. Oops - the output is no longer sorted properly. There might be some workarounds - creating the threads and then starting them after the whole list is read (but that will lead to longer code, against the golf). I wonder if someone can provide a golf that addresses this potential issue...I'm going to try. Jun 2, 2011 at 11:03
• Incidentally, what makes this algorithm really interesting is that there actually exist real-life applications. For instance, DNA sequencing (Sanger sequencing) depends on something like this to sort DNA fragments according to their length (and more generally, every electrophoresis does something similar). The difference is that sequencing is performed physically, not in a computer. Jun 2, 2011 at 12:47
• I hate to be the one to rain on everybody's parade, but doesn't this just offload complexity onto the OS scheduler in a way that's probably O(N^2)? Jun 3, 2011 at 12:25
• I think there are physical sort algorithms that takes O(n) time but O(n) physical objects. Well, we can use melting candles and a tube to do it. en.wikipedia.org/wiki/Spaghetti_sort Jun 3, 2011 at 23:06

C, 127 characters, a rather obvious solution:

main(int c,char**v){
for(int i=1;i<c;++i){int x=atoi(v[i]);sleep(x);printf("%d ",x);}}


(Compiled with gcc -std=c99 -fopenmp sort.c and ignoring all warnings.)

• Cool I really have to learn opemp
– Nils
Jun 2, 2011 at 11:38
• I would call that 93 characters (without command-line parsing and such), but it's impressive that you can do that in only 34 extra characters in C! Jun 2, 2011 at 13:43
• @KonradRudolph - You can save 6 bytes going backwards: for(;c>=0;--c){int x=atoi(v[c]);. Not sure if that's allowed. Jul 6, 2016 at 12:49
• @owacoder that would be for(;--c;)... to leave out v[c] and v[0] which are not part of the list, v[c] == NULL and v[0] == "a.out"
– c--
Jun 20 at 1:21

A kind of lame Perl attempt, 59 55 52 38 32 characters:

map{fork||exit print sleep$_}@a Barebones: 25 Characters: ...if you don't mind the sort results as die output: map{fork||die sleep$_}@a

With all the trimmings:

(for maximum challenge compliance, 44 characters)

sub t{map{fork||exit print sleep$_}@_;wait} If you let perl do the wait for you, 39 characters: sub t{map{fork||exit print sleep$_}@_}

And again, if you don't mind die(), 32 characters...

sub t{map{fork||die sleep$_}@_} Note that in Perl 6, or when the 'say' feature is declared, it is possible to replace the print function with say, saving a character in each instance. Obviously since die both terminates the forked process and writes the output, it remains the shortest solution. • you can stil run perl-E to enable 5.010 features like say – mbx Jun 6, 2011 at 16:33 • (fork&&die sleep$_)for@a works too Oct 21, 2016 at 12:33

## Ruby 1.9, 32 characters

As a function:

s=->a{a.map{|i|fork{p sleep i}}}


If we can just use a predefined variable, it reduces to 25 characters:

a.map{|i|fork{p sleep i}}

• You can save quite some chars by using Thread.new{p sleep i} to print the output. Jun 2, 2011 at 10:32
• @Howard: Good catch, thanks! Jun 2, 2011 at 10:37
• @Ventero, I'm only just learning Ruby and I'd like to know how you would run this lambda function or more specifically how you give this an input. Is it possible to run with IRB? Thanks! Nov 30, 2016 at 1:48

## APL (15 13)

{⎕←⍵⊣⎕DL⍵}&¨⎕


What it does:

¨⎕       : for each element of the input
&        : do on a separate thread
⎕DL⍵    : wait approx. ⍵ seconds
⎕←⍵     : output ⍵

• I see boxes instead of 3 characters. Aug 16, 2012 at 13:02
• @ArtemIce: There are supposed to be three boxes (quads). Two are the I/O variable (reading it gets input, and writing to it prints output), and one is in the name of the ⎕DL function which is sleep. Aug 16, 2012 at 19:05
• Discussing on the APL Orchard, we wonder if ⌊∘⎕DL&¨ would count, for 7; removing the quad on the right makes it a function, ⎕DL is in the ISO SPEC for APL as delaying for "not less than" the time, so flooring its return value of "time actually delayed for" should be valid. Feb 18, 2020 at 7:33

JavaScript, 65 characters (depending on whether you use console.log or something else for outputting the result)

a.map(function(v){setTimeout(function(){console.log(v)},v*1000)})


This assumes that a is an array of non-negative integers and that map() exists on the array prototype (JavaScript 1.6+).

• You can probably shave off two or even three characters by multiplying with 10 (or 9) instead of 1000, without compromising correctness. Jun 2, 2011 at 10:46
• If the one second is intended to remain, you can probably use 1e3 instead.
– Joey
Jun 2, 2011 at 10:56
• @Tomalak, alert is JavaScript's blocking output, prompt is JavaScript's blocking input, and confirm is JavaScript's blocking binary input. If JS were to be written on the command line, those would be the calls you would use. Jun 2, 2011 at 13:13
• @zzzzBov, using blocking output would almost certainly be a bad idea for this task. Jun 2, 2011 at 16:20
• @zzzzBov, it's the order in which they're called which I'm worried about - unless the JS spec has strong guarantees about the order in which setTimeout-enqueued thunks are called. Jun 2, 2011 at 17:36

Four tries in Erlang:

Output to the console, have taken the liberty to do this each 9ms * Number since this is plenty enough to make it work (tested on a Atom embedded board = slow):

Needs 60 chars

s(L)->[spawn(fun()->timer:sleep(9*X),io:write(X)end)||X<-L].


Output to the console is total un-Erlangish, so we send a message to process P instead:

Needs 55 chars

s(P,L)->[spawn(fun()->timer:sleep(9*X),P!X end)||X<-L].


Sending after a time can also be done differently (this even works with 1ms * Number):

Needs 41 chars

s(P,L)->[erlang:send_after(X,P,X)||X<-L].


Actually this is a bit unfair since the built in function send_after is a late comer and needs the namespace erlang: prefixed, if we consider this namespace imported (done on module level):

Needs 34 chars

s(P,L)->[send_after(X,P,X)||X<-L].


## C# - 137 characters

Here is an answer in C# (updated with degrees of parallelism as commented)

void ss(int[]xs){xs.AsParallel().WithDegreeOfParallelism(xs.Length).Select(x=>{Thread.Sleep(x);return x;}).ForAll(Console.WriteLine);}

• You’ll need to specify WithDegreeOfParallelism for this to work, analogously to the num_threads in my OpenMP C code. Jun 2, 2011 at 20:18
• 120 bytes: void m(int[] l){foreach(var i in l){var t=new Thread(()=>{Thread.Sleep(int.Parse(s));Console.Write(s);});t.Start();}}} Jan 27, 2017 at 12:23
• @MrPaulch Note that you need to join the threads again, if you want your program to have the expected behaviour Jan 27, 2017 at 16:28
• Why? The longest running thread will keep the process alive. Jan 27, 2017 at 16:31

# Python - 81 93148150153

Tweaking @BiggAl's code, since that's the game we're playing....

import threading as t,sys
for a in sys.argv[1:]:t.Timer(int(a),print,[a]).start()


... or 97 175 with delayed thread starting

import threading as t,sys
for x in [t.Timer(int(a),print,[a]) for a in sys.argv[1:]]:x.start()


Takes input via the command line, ala

./sleep-sort\ v0.py 1 7 5 2 21 15 4 3 8


As with many python golfs, there comes a point where the code is compact enough that aliasing variables to shorten names doesn't even save characters.

This one is funky though because it aliases sys and threading BOTH as t, so sys.argv becomes t.argv. Shorter than from foo import *, and a net character savings! However I suppose Guido wouldn't be pleased...

Note to self - learn c and stop golfing in python. HOLY COW THIS IS SHORTER THAN THE C SOLUTION!

• I managed to make some tweaks, but the formatting doesn't show up nicely in comments so I made my own answer. daemon doesn't need setting unless you're starting this as a daemon, and it's shorter to use positional args, esp. if you alias None to N Jun 6, 2011 at 12:51
• Oh and the first one doesn't work for me under 2.7.1, as j seems to end up as False - a side-effect of trying to do too much in one line? Jun 6, 2011 at 13:11
• shit I didn't realise you could import multiple modules to the same alias - I could actually think of some uses for that where I have multiple subclasses of the same custom base class lying about in seperate sub-modules. If we can shave off another 30 it's shorter than bash... But I don't think that'll happen. Jun 8, 2011 at 9:15
• Argh the reason why I didn't know is because you can't - I just tried running it and threading is not aliased, it's just called threading. It's sys that is aliased to t... Did you try running this? It's only an extra 2 chars on each though to import as t,s and then change to use s for sys Jun 8, 2011 at 9:29
• why don’t you use the print function instead of sys.stdout.write? Jun 16, 2011 at 19:35

## Java (aka never wins at codegolf) : 234211 187 chars

public class M{public static void main(String[]s){for(final String a:s)new Thread(){public void run(){try{sleep(Long.parseLong(a));}catch(Exception e){}System.out.println(a);}}.start();}}


ungolfed:

public class M {
public static void main(String[] s) {
public void run() {
try {
sleep(Long.parseLong(a));
} catch(Exception e){}
System.out.println(a);
}
}.start();
}
}

• @Joey thanks for setting it straight. Jun 18, 2011 at 19:10
• The class can be non-public, saving 7 chars. Oct 28, 2013 at 1:53
• You could also declare throws Throwable and get rid of the catch clause. Oct 28, 2013 at 2:05
• I think you can save 2 bytes by replacing Long.parseLong with Long.valueOf. Dec 3, 2016 at 15:02
• I know it's been 6.5 years, but you can golf some parts: public and final can be removed; class M{public static void main can be interface M{static void main (Java 8+); Long.parseLong(a) can be new Long(a) (resulting in 165 bytes) Jan 12, 2018 at 12:32

### Scala - 42 40 characters (special case)

If you have a thread pool at least the size of the number of list elements:

a.par.map{i=>Thread.sleep(i);println(i)}


### Scala - 72 characters (general)

a.map(i=>new Thread{override def run{Thread.sleep(i);println(i)}}.start)

• afaik you don’t use {} when staying on one line. Jun 16, 2011 at 19:36
• @flying sheep - You can omit {} with one statement, but you still need it to group things separated by ;, one line or no. And you can write multi-line statements without {} in some cases (if/else for instance). Jun 16, 2011 at 22:33
• oh, i didn’t mean you can omit them, but that you can use () for one-liners instead. it’s a matter of taste there, i think. (i just don’t really get why () are supported at all when {} superseed them. maybe to not alienate java users instantly). Scala is cool, but defining code blocks by indentation is clearly superior. (and so, the religious war ensues ;)) Jun 17, 2011 at 9:59
• @flying sheep - You're misinformed. You can use () for single statements. Try entering (1 to 9).map(i => {val j = i+1; i*j}) in the REPL and then see what happens if you use (1 to 9).map(i => (val j = i+1; i*j)). Jun 17, 2011 at 15:34
• true, but i only referred to for expressions and stuff. Sorry, I hate writing stuff without being able to use linebreaks ;) Jun 17, 2011 at 18:25

# ColdFusion (8+), 109 bytes

<cfloop array="#a#" index="v"><cfthread><cfthread action="sleep" duration="#v*1000#"/>#v#</cfthread></cfloop>


Ungolfed:

<cfloop array="#a#" index="v">
</cfloop>


This assumes that <cfoutput> is in effect. A few characters could be saved by writing it all on one line.

## Javascript - 52 characters

for(i in a)setTimeout("console.log("+a[i]+")",a[i])

• Welcome to CodeGolf.SE! I have formatted you answer for you, in particular indenting your code by four space to make it display as code. You'll find other formatting help in the sidebar of the edit page. Jun 3, 2011 at 0:29

import Control.Concurrent
import System
f x=d(10^6*x)>>print x
g s=mapM(forkIO.f)s>>d(10^6*maximum s+1)


This probably could be made a shorter by taking input on stdin if that were an option, but it's late and either way, it's still 104 characters for the function itself.

# Befunge-98, 38 31 bytes

I know this is an old challenge, but I just recently discovered both sleepsort and 2D languages, had an idea about how to combine them, and looked for a place to post it, so here we are.

&#vt6j@p12<'
v:^ >$.@ >:!#^_1-  The main IP reads a number (&), then hits the t which clones it: one proceeds on the same line and cycles, reading new numbers and generating new childs until it reaches EOF which terminates the sequence. All the child processes get stuck in a closed loop (the v and ^ of the third column) until the main IP finishes reading the input and executes the sequence of commands '<21p, which puts the character < at position (1,2), overwriting the ^ and freeing all the child processes, which start to simultaneously cycle, reducing by 1 their number at each iteration. Since execution speed of different IPs is synchronized in befunge, they will terminate (and print their value) in order, sorting the input list. • 26 bytes by moving the control flow around a bit. – Jo King Jan 12, 2018 at 12:35 A little late to the party: ## Maple - 91 83 characters In 91: M:=():use Threads in p:=proc(n)Sleep(n);:-M:=M,n;end:Wait(map(i->Create(p(i)),L)[])end:[M];  In 83: M:=():use Threads in Wait(seq(Create(proc(n)Sleep(n);:-M:=M,n end(i)),i=L))end:[M];  (This needs Maple version 15, and expects the list to be sorted in L) ## C, 70 69 chars Doesn't wait for child processes to return, otherwise works. main(n) { while(~scanf("%d",&n)?fork()||!printf("%d\n",n,sleep(n)):0); }  ## Haskell, 90 import Control.Concurrent s::[Int]->IO() s=mapM_(\x->forkIO$threadDelay(x*9999)>>print x)


I hope this meets all the requirements.

# JavaScript, 38 bytes

a=>a.map(x=>setTimeout(alert,x*1e3,x))

• This will wait milliseconds instead of seconds Jun 19 at 4:44
• You can use alert to save 6 bytes Jun 19 at 9:52
• @mousetail Oops, didn't catch that it was required to use seconds. Jun 19 at 20:43

<?for(;$i=fgets(STDIN);)pcntl_fork()?:die($i.usleep($i));  pcntl_fork() is only available under linux. Bash (38): xargs -P0 -n1 sh -c 'sleep$0;echo $0'  Edit: Floating-point from stdin, separated by spaces or newlines. # 𝔼𝕊𝕄𝕚𝕟, 11 chars / 22 bytes ïć⇝שĤ⇀ôa,a⸩  Try it here (Firefox only). שĤ⇀ôa, this looks cool. # Rust, 125 bytes Used the depricated sleep_ms function so I don't need to write a long duration. |p:Vec<u32>|p.into_iter().for_each(|i|{use std::thread::{spawn,sleep_ms};spawn(move||{sleep_ms(i*1000);println!("{}",i)});});  playground link Just some tweaking from @rmckenzie 's version: ## Python delayed thread start in 155152114108 107: import sys, threading as t for x in [t.Timer(int(a),sys.stdout.write,[a]) for a in sys.argv[1:]]:x.start()  ## Python without delay in 1301289695 93: import sys,threading as t for a in sys.argv[1:]:t.Timer(int(a),sys.stdout.write,[a]).start()  Managed a few more optimisations, using Timer instead of Thread, which has a more concise call and removed the need to import time. Delayed thread start method benefits from list comprehension as it removes the need to initialise the list seperately at the start, although it's two characters longer ("["+"]"+" "-":") than the for loop so it's useless without delayed start, and you have to be careful to use a list rather than a generator, or you're not actually creating the timer threads until you chunk through the generator. Does anyone else have any optimisations? The trick with as helps, but in 2.7.1 you can only import one module into an alias, and after some playing about you can't even import mod1,mod2 as a,b, you have to import mod1 as a, mod2 as b. It still saves a few characters, but isn't quite the cure-all I thought it was... And in fact it's better to leave sys as sys. Aliasing threading still helps though... • you got me beat, have an upding. I like the x=[];x+=[]. Didn't know you could do that.... Jun 6, 2011 at 13:51 • ... you could do this in 128 if you loose the spaces between the : [statement] in your loop and f(x)... somehow I got it to 127, but I think that's by not counting the final newline (which is legit in CG). Thought I'd give you the update rather than being a tool and stealing your code. Jun 6, 2011 at 14:09 • @rmckenzie go for it, I stole yours. I'm always interested in seeing CG'd python - I feel like I'm doing something very perverse considering the goals of the language... Jun 7, 2011 at 15:05 • Yeah, I'm honestly shocked by how legible most python golfs stay... at the cost of a "glass floor" of characters. Check this one out: import threading,sys as t Jun 7, 2011 at 20:13 ## Clojure, 54 (defn s[n](doseq[i n](future(Thread/sleep i)(prn i)))) • you can get rid of few characters by inlining omitting defn (its brackets + argument list: from 54 to 43 chrs), or use fn instead of defn => len-=2 so I'd say in clj its 43 :D Dec 30, 2014 at 9:34 # C++11, 229 bytes #import<future> #import<iostream> using namespace std;int main(int a,char**v){auto G=new future<void>[a];while(--a){G[a]=move(async([=](){this_thread::sleep_for(chrono::seconds(atoi(v[a])));cout<<v[a]<<" "<<flush;}));}delete[]G;}  Ungolfed and usage: #import<future> #import<iostream> using namespace std; int main(int a,char**v){ auto G=new future<void>[a]; while(--a){ G[a]=move(async( [=](){ this_thread::sleep_for(chrono::seconds(atoi(v[a]))); cout<<v[a]<<" "<<flush; } )); } delete[]G; }  # Rust - 150 bytes And this is why you don't code golf in Rust, it's more verbose than Java ;). Depends on external crate crossbeam, it would be even worse without it. |x|{extern crate crossbeam;crossbeam::scope(|s|for&v in x{s.spawn(move||{std::thread::sleep(std::time::Duration::from_secs(v));println!("{}",v)});})}  Complete test program: fn main() { let z = |x|{extern crate crossbeam;crossbeam::scope(|s|for&v in x{s.spawn(move||{std::thread::sleep(std::time::Duration::from_secs(v));println!("{}",v)});})} ; z(&[4, 2, 3, 5, 7, 8, 9, 1, 6, 10]) }  ## PowerShell 7, 40 bytes filter f{$args|% -Pa{sleep $_;$_}-Th 99}

PS C:\> f 3 2 1
1
2
3


It uses Powershell 7's ForEach-Object -Parallel feature, which defaults to 5 threads, so has -ThrottleLimit 99 to make it at work for the required 10 numbers.

• you can save this code $args|% -Pa{sleep$_;\$_}-Th 99 to a stanalone .ps1 script file. This is a Powershell program. Feb 18, 2020 at 6:02
• @mazzy Nice! this question specifically asks for "a function" including the function definition, so I'm not sure if it counts - if it is valid, it's -10 and would put it around 3rd shortest, which would be good. Feb 18, 2020 at 7:21
• A file with a Powershell script is both a program and a function. So a code that works in a standalone .ps1 file fits perfectly Feb 18, 2020 at 7:27

# Julia 1.0, 41 bytes

!l=@sync l.|>i->@async sleep(i)println(i)


Try it online!

@async adds the task to the machine's scheduler queue, and @sync waits for all @asyncs to finish

# C (clang), 72 bytes

main(n){~scanf("%d",&n)?fork()?wait(main()):printf("%d ",n+sleep(n)):0;}


I chose clang but it also works on gcc.

1. takes input from stdin
2. fork()
3. if it's the child, then sleep (returns 0 if sleep succeeded, see sleep(3)) and print the number... if it's the parent call main recursively (which implicitly returns 0 since C99).
4. when there's no more input we return from main() and start waiting for the children, the children also call wait() a number of times depending on the recursion depth but they don't have any children so that fails immediately for them.

Try it online!

Kind of boring, port of C#, just to get started with the language again:

F# - 90 characters

PSeq.withDegreeOfParallelism a.Length a|>PSeq.iter(fun x->Thread.Sleep(x);printfn "%A" x)