ポーカー、プログラミング、もぐ

ポーカーとプログラミングともぐもぐについてのブログ。

マージソート at Python

組み込みのを使うのが普通なのだけど、まあ頭の体操がてら。

def mergesort(lst):
    if not isinstance(lst, list):
        raise ValueError("argument must be list")

    if len(lst) < 2:
        return lst

    lst1 = lst[:int(len(lst)/2)]
    lst2 = lst[int(len(lst)/2):]

    sorted_lst1 = mergesort(lst1)
    sorted_lst2 = mergesort(lst2)

    result = _merge(sorted_lst1, sorted_lst2)
    return result

def _merge(lst1, lst2):
    result = []

    total = len(lst1) + len(lst2)
    while len(result) < total:
        if  len(lst1) == 0:
            result.extend(lst2)

        elif len(lst2) == 0:
            result.extend(lst1)

        elif lst1[0] < lst2[0]:
            result.append(lst1[0])
            lst1.pop(0)

        else:
            result.append(lst2[0])
            lst2.pop(0)

    return result

ソートにもいろいろあるけど、私はこのマージソートが一番好きですね。
半分こしていって最後に結合していくのがなんかいいかんじ。