ベストアンサー
マージソートを実装して再帰呼び出しで配列を作成すると、それらの多くは、同時に共存することはありません。すべての再帰呼び出しで、マージ用の配列（または実装によっては2つ）を作成し、O（n）スペースしか必要とせず、マージするときに完了すると、これらの配列は削除され、他の再帰呼び出しでしばらくすると新しい配列が作成されます。これまでに作成されたすべての配列にかかったスペースを数えると、O（n log n）、ただし、この情報を気にする必要はありません。配列を作成する必要がある場合、他のすべての配列は存在せず、メモリを占有しないため、O（n）を超えるスペースは必要ありません。 。最初に2つまたは3つの配列を宣言し、それぞれの長さをnにして、シーケンスを一方に格納し、もう一方をマージに使用すると、パフォーマンスが向上するだけでなく、それ以上のことを示すことができます。 O（n）を超えるメモリは必要ないのではないかと疑っています。
回答
2つのソートされた配列をマージするときのマージソートでは、2つの一時配列を作成します。L[ ] = Arr [left、mid]（left array）は古い配列を左から中央に一時的に保存し（左半分にソート）、R [] = Arr [mid + 1、right]（right array）は古い配列を一時的に保存します中央+1から右（右半分にソート）まで、2つの一時配列を元の配列にマージします。元の配列には一時的な要素がn個あるため、元の配列の番号を格納するために2つの一時配列を作成するという事実配列のサイズはそれぞれnであるため、nの余分なスペースとO（n）スペースの複雑さ。ある種のスペースの複雑さを計算するときに、配列の元のスペースは考慮されません。アルゴリズムを使用します。