アルゴリズムクイックリファレンス 第2版

92

■

4

章 整列アルゴリズム

if j >= end or (i < mid and A[i] < A[j]):

result[idx] = A[i]

i += 1

else:

result[idx] = A[j]

j += 1

idx += 1

4.7.4

 分析

マージソート

は、範囲

A[start, end)

の左半分と右半分とを再帰的に整列し、適切

に順序付けた要素を

result

で参照されている配列へ格納して、「併合」段階を

O(n)

時間で終える。

mergesort_array(array1, array2, start, end)

関 数 は、

array1[start, end)

を

array2[start, end)

の整列したもので上書きする。再帰の基底において、

2

要素だけ

なら

array2[start, end)

が

array1[start, end)

と全く同じ要素になっている。だから、

array2

の要素を直接操作できる。これは、

array2

が最初に

array1

の完全なコピー

になっているからだ。

array1

の要素が

3

個以上なら、再帰呼び出しで、配列参照を

スワップして、

array2[start, mid)

を整列したもので

array1[start, mid)

を上書きし、

array2[mid, end)

を整列したもので

array1[mid, end)

を上書きする。

array1[start,

end)

の整列した半分ずつの配列は、併合されて整列配列

array2[start,