On: Sleep sort (2011)

[danso]

Sadly, the somewhat lengthy Wikipedia entry for Sleep sort was deleted. Here's archive.org's version:

https://web.archive.org/web/20110622073615/http://en.wikiped...

Reading through Wikipedia's existing pages for other esoteric sorts makes me laugh as I did when reading Hitchhiker's Guide to the Galaxy's various entries for scientific theories (e.g. Bistromathics)...There's Bogosort, Stooge sort, American flag sort, and my favorite, "Gnome sort", named thusly because "that is 'how a gnome sorts a line of flower pots'" http://en.wikipedia.org/wiki/Gnome_sort

[chriswarbo → danso]

I like the comparison between the incredibly inefficient Bogosort:

    1) Shuffle the list.
    2) If it's sorted, halt.
    3) If it's not sorted, go to step 1.

and the incredibly efficient Quantum Bogosort:

    1) Shuffle the list.
    2) If it's sorted, halt.
    3) If it's not sorted, destroy the Universe.

According to the Many Worlds interpretation, step (1) creates multiple Universes, each with a different ordering of the list. Step (3) ensures that, by the anthropic principle, we must be in a Universe where the list was sorted correctly (otherwise we wouldn't be around to observe anything).

[TheSoftwareGuy → chriswarbo]

how does it destroy the universe though? I am really not very familiar with things in the quantum world and that kind of stuff.

[chriswarbo → TheSoftwareGuy]

That's an implementation detail ;)

[bane → danso]

Of course, why wouldn't WP delete it? <sarcasm>

I just found out that the WP page for the hornet archive, one of the most important focal points of the international demoscene for a decade, was deleted because it was't "notable".

So frustrating.

[angersock → bane]

Shame, isn't it?

[seabee → danso]

Unlike most esoteric algorithms, American flag sort is actually pretty useful in its niche of string sorting.

[Al-Khwarizmi → danso]

Gnome sort used in a practical application (for natural language parsing): http://stp.lingfil.uu.se/~nivre/docs/gotal.pdf

[drcomputer → danso]

But why. I would think the gnome is the perfect size to pick up exactly one flower pot (the next smallest) and would also be able to recall a dividing line (because the gnome is tiny and prefers traveling less).