Sleep sort

Everyone likes algorithms, especially novel sorting algorithms. So the basis for this “sleep sort” is simple: take the first element n of the array (of positive integers), fork a new process which sleeps n seconds then displays that number. Repeat for the next element.

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

Calculation of the average (and worst-case) complexity of this algorithm is left as an exercise to the reader; you might also enjoy bogosort and stooge sort (as well as some dancing).

6 thoughts

  1. Having spent most of my early sorting days working with physical objects (large, bulky medical records), I’m always curious about how a sorting algorithm translates into a physical metaphor: for example, insertion sorts can be physically painful, since inserting heavy files into tight shelves can result in trapped fingers and ripped cuticles; caching involves keeping frequently accessed records in a different cabinet. You can imagine the rest.

    I’m not quite sure how the sleep-sort translates, though: maybe we spread the items on a desk and have a person attached to each one with a clock? Not efficient in terms of human effort, but maybe that’s cheap?

    As an aside, I’m now intrigued that I naturally think of the physical sorting of objects as a metaphor for a computational sorting algorithm. That says something about me, but I’m not sure what. (And I don;t want to know …)

    1. Interesting — I like the idea of identifying real-world analogies for computational (sorting) algorithms, could be useful in the classroom.

      However…I fear that this may be futile for sleep sort (which is essentially a type of bucket sort, but effectively time-based rather than space-based) et al. Is it hard to find a real-world grounding because it is deliberately nonsensical? (can you find an analogue for bogosort?)

      1. A real-world analogue doesn’t have to be a *sensible* real-world analogue; in fact, the absence of a sensible real-world analogue *might* give us some insight into the merit of the computational algorithm.

        But while that”s (to me) an interesting line, I’m not sure it can realistically give us any useful measure of utility.

  2. Extending this think further, would it be possible to super-optimize a sort routine based on an architecture with an underlying set of primitives that are physically viable without pain?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.