# How can we implement "Sleep Sort"?

Inspired by 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 would like to know if it is possible to implement this in Mathematica. As a version 7 user I would of course like to see a solution that works there, but I think that RunScheduledTask may be needed to accomplish this.

• Sorry for not reading the link carefully! Got it now :-) That extra sentence makes a huge difference. Gave an answer and +1 Jan 22, 2012 at 10:53

Here is an implementation that uses the scheduled tasks in version 8:

sleepSort[l_, t_:0.1] :=
Scan[RunScheduledTask[Print[#];RemoveScheduledTask[$ScheduledTask], {t #}]&, l]  In a notebook environment, output will appear in the messages window. The time interval is specified as the optional second argument, defaulting to 1/10th of a second (I'm impatient). Don't set it too low, though -- the vagaries of the timing might produce results out of order. • brilliant ! I believe we do not need necessarily need RemovScheduledTask[$ScheduledTask] because this sleepSort[L_List, t_: 1] := Scan[RunScheduledTask[Print[#], {t #}] &, L] works equally well Feb 5, 2017 at 15:04
• @AliHashmi It is not necessary to call RemoveScheduledTask, but if we don't then the list of ScheduledTasks[] will grow indefinitely. It is good practice to clean up scheduled tasks when they are no longer needed, just as we should close opened files after using them. Feb 5, 2017 at 16:59

Here is my attempt to do this with a single kernel. Output is printed directly to the messages channel, and you cannot suppress the output of f /@ list because if the Dynamic expressions never display they never run.

list = RandomInteger[10, 10]
f = Module[{x},
(x := If[start + # < AbsoluteTime[], Print[#]; x =.]);
Dynamic[Refresh[x, UpdateInterval -> 1]]
] &;

start = AbsoluteTime[]; f /@ list

• This is not an attempt, it's a solution. I like better like this: change Print[#] to AppendTo[result,#], set result = {} at the beginning, and put a Dynamic[result] somewhere to watch it in real time. Jan 22, 2012 at 12:13

Note: While this whole post is just playing, the idea for the solution comes from an answer to a very real problem I had, so it wasn't just a futile exercise. The key is that (in v8) a shared function (set with SetSharedFunction) is always evaluated on the main kernel. Thanks to Andrew Moylan for pointing this out!

Here's my incredibly wasteful solution that makes you run out of kernel licenses:

In[16]:= CloseKernels[] (* just in case *)

In[17]:= list = RandomInteger[10, 10]
Out[17]= {3, 2, 10, 8, 1, 0, 5, 10, 8, 10}

In[18]:= LaunchKernels@Length[list]

In[19]:= ParallelSow = Sow
SetSharedFunction[ParallelSow]

Out[19]= Sow

In[21]:= Reap@ParallelDo[Pause[i]; ParallelSow[i], {i, list}]
Out[21]= {Null, {{0, 1, 2, 3, 5, 8, 8, 10, 10, 10}}}

In[22]:= CloseKernels[]


EDIT

Another solution, should be v7 compatible. Just evaluate all of it at once.

CloseKernels[];

list = RandomSample@Range[10]

LaunchKernels@Length[list];

jobs = {ParallelSubmit /@ ((Pause[#]; #) &) /@ Hold @@ list} //
ReleaseHold

Reap@NestWhile[Function[j, (Sow[#1]; #3) & @@ WaitNext[j]],
jobs, # =!= {} &]

CloseKernels[];


• I wanted to show it works even if the list has duplicates. I don't know how precise Pause is though ... Jan 22, 2012 at 10:57
• I'm sorry, I forgot 7 doesn't have SetSharedFunction! Jan 22, 2012 at 10:59
• Stay tuned, v7 version is compatible coming Jan 22, 2012 at 11:00
• Incidentally it appears to work if I use Sow rather than ParallelSow, or simply Print. Jan 22, 2012 at 11:01
• @Mr.Wizard See my edit Jan 22, 2012 at 11:18

Here's a version that cheats and works by using bash (or probably almost any other *nix shell). It places the sorted list into the file tmp in the current directory.

sleepSort[lst_?(VectorQ[#, Positive] &)] :=  Do[
Run["(sleep " <> n <> "; echo " <> n <> " >> tmp)&"], {n, ToString/@lst}]


See the output at Mathematica/Bash sleep sort