Hacker News new | past | comments | ask | show | jobs | submit login

One of my favourite papers of all time.

Most of the paper is a good joke, but Slowsort takes it a step further. It is just so inefficient I can’t help but laugh out loud each time I revisit the paper and re-understand the algorithm.

It ticks all the nice boxes, such as being easily proven correct, easy to implement, easy to parallelize, stable, no time wasted on unnecessary steps, can produce output as it sorts the rest.

At the same time, it’s Mergesort with a ridiculous merging step. But that means one can simply add a parameter to tune between Mergesort and Slowsort – if(rand(1,10) > 8) then slow else merge – so the code becomes tunable in terms of speed. Someone needs faster software? OK, I’ve got just the parameter for you :-D

If you haven’t implemented it yourself, give it a shot. It’s a transformative experience to see your computer struggle sorting an already sorted 100-entry array ;-)

Slowsort seems to be another name for the (to me) more common name Bogosort:


Slowsort is guaranteed to take a long time but Bogosort could finish in one step.

Bogosort is at best linear, since we have to check if the list is sorted.

Quantum Bogosort guarantees the best performance, since it destroys all universes where the list remains unsorted after the first shuffle.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact