クイックソート
分割の操作自体は追加の領域を必要としないが、再帰によるコールスタックの消費が空間計算量となる。スタックの消費は平均的には O ( log  n ) {\displaystyle O(\log n)} となるが、最悪ケースでは O ( n ) {\displaystyle O(n)} に増大するため、大きなサイズの配列の場合スタックオーバーフローを起こす危険性がある。
対策として、「分割された配列のうち、要素数が少ない方を常に先に処理する」ことで、空間計算量を最悪 O ( log  n ) {\displaystyle O(\log n)} に抑えられる。このようにすると、常に均等に分割される(最良時間の)場合に log  n {\displaystyle \log n} スタックとなる一方で、1要素ずつしか分割されない(最悪時間の)場合には定数スタックで済む。
これを実装するには、明示的なスタックを用いて非再帰(ループ)構造とするか、(末尾再帰の最適化機能があれば)要素数が多い方を末尾再帰で処理すればよい。
また、イントロソートによっても最悪 O ( log  n ) {\displaystyle O(\log n)} 空間を保証できる(再帰深さの閾値が log  n {\displaystyle \log n} となるように設定すればよい)。