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

4.7

 外部ストレージのある整列

■

91

4.7.2

 入出力

整列出力は元の集まり

A

の場所に返される。内部ストレージ

copy

は破棄される。

4.7.3

 解

マージソート

は、左および右の整列済み部分配列を、

2

つの添字

i

と

j

とで左（お

よび右）要素上を走査しながら、

A[i ]

と

A[ j ]

のうちより小さい方を本来の位置

result[idx ]

にコピーすることを繰り返して併合を行う。

3

つの場合を考えなければ

ならない。

●

右側の要素がなくなる（

j

≧

end

）、この場合残りの要素は左側から取られる。

●

左側の要素がなくなる（

i

≧

mid

）、この場合残りの要素は右側から取られる。

●

左右に要素がある。

A[i ]

＜

A[ j ]

なら

A[i ]

を挿入、さもなくば

A[ j ]

を挿入。

for

ループが完了すると、

result

には、元の

A[start, end)

の併合（かつ整列）した

要素がある。例4-10に

Python

による実装を示す。

例

4-10

 

Python

によるマージソート実装

def sort (A):

""" A

をその場でマージソート

"""

copy = list(A)

mergesort_array (copy, A, 0, len(A))

def mergesort_array(A, result, start, end):

"""

与えられた範囲のメモリで配列のマージソート

"""

if end - start < 2:

return

if end - start == 2:

if result[start] ...