Python

Pythonで学ぶアルゴリズム ソート マージソート

  /

マージソートを実装してみます。

概要

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。

マージソート – Wikipedia

サンプルコード

import random


data_len = 10
data = random.sample(range(1, 42), data_len)
print(data)


def merge_sort(collection: list) -> list:

    def merge(left: list, right: list) -> list:

        def _merge():
            while left and right:
                yield (left if left[0] <= right[0] else right).pop(0)
            yield from left
            yield from right
        return list(_merge())

    if len(collection) <= 1:
        return collection
    mid = len(collection) // 2
    return merge(merge_sort(collection[:mid]), merge_sort(collection[mid:]))


print(merge_sort(data))

実行結果（例）

[9, 6, 5, 2, 19, 35, 30, 22, 14, 37]
[2, 5, 6, 9, 14, 19, 22, 30, 35, 37]
RELATED POST