ワンライナーでマージソートを実装したい（Python3）

Pythonはインデントで構造化されている設計上、ワンライナー(一行だけで動作するコード)を書くことが難しい言語ですが、だからこそPythonでのワンライナーは面白いのです。

コード

def merge_sort(arr): return arr if len(arr) <= 1 else None if (l := merge_sort(arr[:len(arr)//2])) and (r := merge_sort(arr[len(arr)//2:])) and False else [l.pop(0) if l and r and l[0]<=r[0] else (r.pop(0) if r else l.pop(0)) for _ in range(len(arr))]

みやすく

def merge_sort(arr):
    return arr if len(arr) <= 1 \
        else None if (l := merge_sort(arr[:len(arr)//2])) \
                    and (r := merge_sort(arr[len(arr)//2:])) \
                    and False \
        else [
            l.pop(0) if l and r and l[0]<=r[0] else (r.pop(0) if r else l.pop(0))
              for _ in range(len(arr))
            ]

解説

展開すると以下のようになります。

def merge_sort(arr):

    # 再帰の終了条件
    if len(arr) <= 1:
        return arr
        
    # left, rightに分割
    l = merge_sort(arr[:len(arr)//2])
    r = merge_sort(arr[len(arr)//2:])

    # mergeする
    return [l.pop(0) if l and r and l[0]<=r[0] else (r.pop(0) if r else l.pop(0)) for _ in range(len(arr))]

一番苦労したmerge操作の部分ですが、下のように実装してみました。

# mergeの原型
res = []
while l and r:
    if l[0] <= r[0]:
        res.append( l.pop(0) )
    else:
        res.append( r.pop(0) )
res += l + r

# for文で書き換え
res = []
for _ in range(len(l) + len(r)):
    if l and r and l[0] <= r[0]:
        res.append( l.pop(0) )
    elif r:
        res.append( r.pop(0) )
    else:
        res.append( l.pop(0) )  # lだけに残っている場合

# 内包表記にまとめる
[l.pop(0) if l and r and l[0]<=r[0] else (r.pop(0) if r else l.pop(0)) for _ in range(len(arr))]

また、下のような謎の式が入っているのは

... if (l := merge_sort(arr[:len(arr)//2])) \
        and (r := merge_sort(arr[len(arr)//2:])) \
        and False \
    else ...

入力arrをleft, rightの二つのリストに分割するためです。代入文を書くためにわざわざ3項演算子の中でセイウチ演算子:=を使うという回りくどい構造になってます。

おまけ

世界中のワンライナー好きが集うone-line-wondersというgithubリポジトリがあったりします。

この記事はAttribution-NonCommercial Use-ShareAlike 4.0 Internationalライセンスの元に提供されています。