display | more...

Spaghetti sort is a sorting algorithm that runs in O(n) time. Here's how it works:

You can only sort positive real numbers, or there needs to be a one-to-one mapping from the values that you want to sort to the set of positive real numbers. Without loss of generality, let's assume that we are sorting values from the set of natural numbers

For each value that you want to sort, cut a piece of spaghetti so that it has a length in inches equal to the value you want to sort. This cutting takes O(1) time for each value, for a total of O(n) for all n values.

Now, take all of these pieces of spaghetti in your hand and put them down on a table so that all the pieces are lined up at one end. The tallest piece is the largest value, the next tallest is the next largest, etc. Since you are simply inspecting all the spaghetti that you have in your hand, you find the largest value in constant time. To then put the values down in order takes O(n), for an overall linear running time for the algorithm.


cordelia insists that I add a disclaimer to this node, indicating that it is meant to be humorous, and not an implementable sorting algorithm.

Log in or register to write something here or to contact authors.