ストランドソートを使用する

ストランドソート (strand sort) は、未整列の区間を左から一度走査し、先頭から続く単調非減少部分列（ストランド）だけを抜き取り、それをすでに得られている整列済みの結果と マージ（併合） することを繰り返す比較ソートである。「麻ひも・繊維束（strand）をほどく」イメージで、1 本のストランドをずつ取り出して束ね直していく。

  1. 初期化: 整列済み結果 R は空、P に入力をそのまま置く。
  2. ストランド抽出: P を左から見て、直前にストランドへ入れた末尾の値 以上 の要素だけを順にストランドへ移す（末尾より小さい値は見送り、インデックスだけ進める）。1 回の走査でストランドは必ず 1 要素以上になる。
  3. マージ: R とストランドはどちらも昇順なので、マージソートと同様に先頭同士を比較しながら併合し、新しい R とする。P に残った要素はそのまま次のラウンドへ。
  4. 終了: P が空になるまで手順 2〜3 を繰り返す。

最悪では 1 要素ずつしかストランドが伸びず、マージは合計で O(n²) 相当になる。マージを 安定 に実装（同値では常に R 側を先に取るなど）すれば、全体も安定ソートにできる。ストランドの取り出しとマージの双方で 追加配列 を使う実装が一般的で、空間計算量は実装次第だが O(n) 程度を要しやすい。

procedure strand_sort(input)
  R = empty list
  P = copy of input
  while P is not empty
    strand = empty list
    i = 0
    while i < length(P)
      if strand is empty or P[i] >= last(strand) then
        append P[i] to strand
        remove P[i] from P
      else
        i = i + 1
    R = merge(R, strand) // both sorted; stable if merge breaks ties toward R
  return R

教育用・挙動の可視化にはわかりやすい一方、一般用途の標準ソートとしてはクイックソートやティムソートなどに比べ不利になりやすい。マージの性質を理解する教材として、マージソートと対比して読むと理解が進みやすい。