3秒でわかる
配列を半分ずつに分け、整列済みの列を併合して並べ替える手法。どんな並び順の入力でも速度が落ちず、同じ値どうしの順序も入れ替わりません。
30秒図解
もう少し詳しく
どういうものか
マージソートは、配列を真ん中で 2 つに割る作業を要素が 1 個になるまで繰り返し、そこから 2 本ずつ突き合わせて小さいほうから取り出しながら 1 本に戻していく並べ替えです。要素 1 個の列はすでに整列済みとみなせるので、あとは「整列済みの 2 本を整列済みの 1 本にする」作業だけを繰り返せば全体が揃います。
なぜ必要か
計算量が常に O(n log n) で、データの並びに影響されない点が価値です。クイックソートは平均こそ速いものの、すでにほぼ整列済みの入力に対して選び方を誤ると O(n^2) まで落ちます。マージソートは最悪の場合でも同じ速度を保つため、応答時間を保証したい場面で選ばれます。同じ値の順序が入れ替わらない安定ソートである点も、複数条件で並べ替えるときに効いてきます。
具体例
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
return merge(left, right)
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2]))分割の様子は下のようになります。
[5,3,8,1] -> [5,3] [8,1] -> [5][3][8][1]
併合 -> [3,5] [1,8] -> [1,3,5,8]
