スパゲティソート
アルゴリズム考案者のデュードニー自身が、スパゲティの並べ替えに例えて説明している。
長さが不揃いの乾燥スパゲティの束があったとする。これを手で軽く握ってテーブルの表面に立てる。
次に、もう一方の手を上から降ろしていき、最初に触った棒を取り出す。これが一番長い棒となる。この棒をリストの最初に追加する。さらに手を降ろしていき、次に触れた棒をリストの2番目に追加する。全ての棒が無くなるまで、この手順を繰り返す。
これをコンピュータアルゴリズムとして使う場合、並べ替えに必要な時間として、(1)与えられた数列と同じ長さのスパゲティを準備する時間、(2)スパゲティを並べ替える時間、(3)並べたスパゲティを数字に変換する時間が挙げられる。これらの時間は全てスパゲティの本数に比例する。
つまり、棒の数が n {\displaystyle n} 倍になれば、並べ替えに必要な時間も n {\displaystyle n} 倍となる。これをいわゆるランダウの記号で表すと、 O ( n ) {\displaystyle O(n)} となる。 これは、一般的なソートアルゴリズムの時間計算量が O ( n 2 ) {\displaystyle O(n^{2})} や O ( n log  n ) {\displaystyle O(n\log n)} である(ソート#ソートアルゴリズムの一覧)ことを考えると、珍しい特性である。