ビーズソート
ビーズソートは、計算複雑性が異なる4種類の実装が可能である。
O(1): ビーズは落下距離にかかわらず単位時間で落下するとするモデル。実際には実装できない抽象化されたビーズソートである。
O( n {\displaystyle {\sqrt {n}}} ): 重力を用いる物理モデル。落下距離は時間の2乗に比例するため、落下時間はデータの数の平方根に比例する。
O(n): ビーズが等速で移動するモデル。ソフトウェアでの実装では、下にビーズがあるかを確認するため、この時間計算量が相当する。
O(S): Sはビーズの総数であり、ソフトウェアでの実装では、各ビーズに対して落下可能かを確認する効率的なアルゴリズムが存在しない場合、この計算量となる。
鳩の巣ソートのように、ビーズソートの最悪計算量がO(nlog)を下回る点で珍しく、最良計算量は比較ソートの最悪計算量である。ビーズソートの要素は非負整数であり、その制約を利用するため、このような高速なソートが可能である。