Smoothsort Demystified

Last Major Update: January 7, 2011 A few years ago I heard about an interesting sorting algorithm (invented by the legendary Edsger Dijkstra) called smoothsort with great memory and runtime guarantees. Although it is a comparison sort and thus on average cannot run faster than Ω(n lg n), smoothsort is an adaptive sort, meaning that if the input is somewhat sorted, smoothsort will run in time close

[kazuhooku]

メモリ使用量がO(1)で最悪実行時間がO(log N)でソート済だとO(N)なソートアルゴリズムの説明。レオナルド木...