三分割クイックソート (3-way Quick Sort)

**三分割クイックソート (3-way Quick Sort)**は、ピボットを基準に列を分割して再帰的に整列するソートである。

仕組み

ピボット未満と以上の区間へpartitionし、各区間に同じ処理を適用する。

計算量・性質

平均O(n log n)、偏った分割が続くと最悪O(n²)。in-place版の平均補助領域は再帰スタックO(log n)。

具体例

[4,1,3,2]で3をピボットにすると[1,2]・3・[4]へ分かれる。

限界と注意点

ピボット戦略と重複値処理が性能を左右し、一般には安定ソートではない。