Spaghetti sort

[1][2][3] This algorithm sorts a sequence of items requiring O(n) stack space in a stable manner.

It requires a parallel processor, which is assumed to be able to find the maximum of a sequence of items in O(1) time.

For simplicity, assume we are sorting a list of natural numbers.

Lowering the rods on the table takes constant time, O(1).

This is possible because the hand, the spaghetti rods and the table work as a fully parallel computing device.

Schematic diagram of spaghetti sorting. The spaghetti can be sorted by removing them from the bundle on the table in the order they stick out.