# 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 – Szabolcs Jan 22 '12 at 10:53

## 4 Answers

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.

-

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 ... – Szabolcs Jan 22 '12 at 10:57
I'm sorry, I forgot 7 doesn't have SetSharedFunction! – Szabolcs Jan 22 '12 at 10:59
Stay tuned, v7 version is compatible coming – Szabolcs Jan 22 '12 at 11:00
Incidentally it appears to work if I use Sow rather than ParallelSow, or simply Print. – Mr.Wizard Jan 22 '12 at 11:01
@Mr.Wizard See my edit – Szabolcs Jan 22 '12 at 11:18

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. – Szabolcs Jan 22 '12 at 12:13

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

-