[Python]collection.dequeを使ってマージソートをする

実現したいもの

Pythonを用いたマージソートを実装する。

まずは普通に

両端キューを使わずに実装してみる。

def merge_sort(a):
    # 空配列の場合は返す
    if len(a) <= 1:
        return a

    n = len(a)
    x = n / 2
    l, r = [], []

    # 分割
    for i in range(n):
        if i < x:
            l.append(a[i])
        else:
            r.append(a[i])

    # 再帰関数の呼び出し
    l = merge_sort(l)
    r = merge_sort(r)

    # 結合
    merged = []
    merged.extend(l)
    r.reverse()
    merged.extend(r)

    b = []
    while len(merged) != 0:
        first = merged[0]
        last = merged[len(merged)-1]
        if first <= last:
            b.append(first)
            del merged[0]
        else:
            b.append(last)
            del merged[len(merged)-1]

    return b

n = int(input())
a = list(map(int, input().split()))
sorted_a = merge_sort(a)
print(*sorted_a)

l, rの結合処理に注目してほしい。

# 結合
    merged = []
    merged.extend(l)
    r.reverse()
    merged.extend(r)

    b = []
    while len(merged) != 0:
        first = merged[0]
        last = merged[len(merged)-1]
        if first <= last:
            b.append(first)
            del merged[0]
        else:
            b.append(last)
            del merged[len(merged)-1]

mergedという空配列を準備し、両端の値を比較、小さいほうを別の配列bに移動している。

問題点

Pythonのlistにおける先頭の要素の削除は、後続の要素をすべて前にずらす関係上 計算量が $O(N) $ になるという弱点がある。
そのため、(first <= last) == Trueが続くような入力パターンに弱い。

改善案

collections.dequeを利用する。

Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

実装例

from collections import deque

def merge_sort(a):
    # 空配列の場合は返す
    if len(a) <= 1:
        return a

    n = len(a)
    x = n / 2
    l, r = [], []

    # 分割
    for i in range(n):
        if i < x:
            l.append(a[i])
        else:
            r.append(a[i])

    # 再帰関数の呼び出し
    l = merge_sort(l)
    r = merge_sort(r)

    # 結合
    dq = deque()
    dq.extend(l)
    r.reverse()
    dq.extend(r)

    b = []
    while len(dq) != 0:
        first = dq[0]
        last = dq[-1]
        if first <= last:
            b.append(dq.popleft())
        else:
            b.append(dq.pop())

    return b

n = int(input())
a = list(map(int, input().split()))
sorted_a = merge_sort(a)
print(*sorted_a)

参考