マージソート

マージソート

マージソートは、ソートしたいデータが入ったリストを２つに分割することを繰り返し、すべてがバラバラになった状態から、これらのリストを統合（マージ）する方法です。

この統合する際に、そのリスト内で値が小さい順に並ぶように実装することで、全体が１つのリストになったときには全ての値がソート済みになっています。

ソースコード

マージソートを実装すると下記のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
lst = [13, 7, 9, 11, 5, 7, 2, 4, 15, 6]

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2    # 半分の位置を算出
    # 再帰的に分割
    left = merge_sort(lst[:mid])   # 左側を分割
    right = merge_sort(lst[mid:])  # 右側を分割
    # 統合
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0

    while (i < len(left)) and (j < len(right)):
        if left[i] <= right[j]:         # 左 ≦ 右　の場合
            result.append(left[i])      # 左側から１つ取り出して追加
            i += 1
        else:
            result.append(right[i])     # 右側から１つ取り出して追加
            j += 1
    
    # 残りをまとめて追加
    if i < len(left):
        result.extend(left[i:])         # 左側の残りを追加
    if j < len(right):
        result.extend(right[j:])        # 右側の残りを追加
    return result

print('解：', merge_sort(lst))

[実行結果]

解： [2, 5, 6, 6, 7, 6, 9, 9, 13, 15]

マージソートの特徴

マージソートの特徴として、メモリに入りきらないような大容量のデータにも使えることが挙げられます。

分割した領域のそれぞれでソートできるため、複数のディスク装置にあるデータをそれぞれでソートしておき、それを結合しながらソート済みのデータを作成することも可能です。