マージソートは時間計算量がO(n log n)(nはソートされるレコードの個数)であり高速であるが,内部ソートとして実行する場合,作業場所として大きさnの配列を要するのが欠点であるとされている.本論文では,作業場所として数語だけを要するマージソートを提案する.新しいマージソートの時間計算量はO(n log^2 n)であり,従来のアルゴリズムより悪いが,これは作業場所とのトレードオフの結果である.Mergesort is one of the fastest sorting algorithm, since it requires only O (n log n) of computing time. Mergesort, however, requires an array of size n as working area, when executed as an internal sort. In the present paper, we propose an algorithm which is a modified version of mergesort. The space complexity of the proposed algorithm is only O. The time complexity is O (n log^2 n), which is worse than the existing merge sort and is the result of the tradeoffs between time and space complexities.