メモリに収まらない可能性のある大きなファイルをソートするプログラムを実装しています。すべてのファイルは行でソートされるので、リストを使用してそれを行うことを考えています。
ファイルを小さなファイルに分割するためにメモリ内に何行持つことができるかはすでに計算しましたが、N個の要素のリストを並べ替えるためにメモリ内に必要なスペースの数がわかりません。
問題は、要素の最大数（既知のサイズの文字列）と使用可能なメモリを知っている場合、List.Sortメソッドに必要なメモリのスペースはどれくらいかということです。
List<T>.SortO（log n）スペースであるクイックソートアルゴリズムを使用します。
クイックソートはO(logn)、すべての再帰レベルで一定の情報（パーティションの開始と終了）を格納し、ほとんどのlognレベルで存在するため、スペースが複雑になります。
バブルソートのフォールバックと同様に、マージ自体はインプレースであるため、それらはO(1)カウントされません。
調査を行います。List.Sort（）はデフォルトでQuickSortアルゴリズムを使用しますが、これにはO（logn）スペースの複雑さがあります。
スペースの複雑さが本当に心配で、遅いアルゴリズムを気にしない場合は、 O（1）スペースの複雑さを持つバブルソートを使用できます。