Time and Space Complexity

時間計算量:

• 平均的な場合: O(n log n)
  • バランスの取れたピボットは、毎回配列をほぼ半分に分割し、約 log n レベルの O(n) の分割作業が発生します。
• 最悪の場合: O(n²)
  • ピボットが常に最小または最大の要素である場合（例えば、最後の要素をピボットとする既にソート済みの配列など）、毎回片側が空になり、再帰の深さは n レベルになります。

空間計算量:

• ここで作成するバージョンでは、各ステップで新しい小さなリストと大きなリストを作成するため O(n) です。古典的な in-place クイックソートでは、これを O(log n) の追加空間に改善します。

まとめ:

• クイックソートは平均的に非常に高速であり、実務でよく使われるソートアルゴリズムです。
• 不適切なピボットの選択は O(n²) に低下させる可能性がありますが、適切なピボット戦略（ランダムな要素や中央値を選択するなど）によってこれを回避できます。