Pythonでマージソート

マージソートをPythonで書いてみました。

def merge(a, b):
c = []
while len(a) > 0 and len(b) > 0:
if a[0] < b[0]:
c.append(a.pop(0))
else:
c.append(b.pop(0))
return c + a + b

def mergesort(a):
num = len(a)
if num <= 1:
return a
else:
k = num // 2
x = a[0:k]
y = a[k:num]
x = mergesort(x)
y = mergesort(y)
return merge(x, y)

上のコードはソート部分とマージ部分を分けていますが一つの関数にまとめると次のとおりです。

def mergesort(a):
c = []
x = []
y = []
num = len(a)
if num <= 1:
return a
else:
k = num // 2
x = a[0:k]
y = a[k:num]
x = mergesort(x)
y = mergesort(y)
while len(x) > 0 and len(y) > 0:
if x[0] < y[0]:
c.append(x.pop(0))
else:
c.append(y.pop(0))
return c + x + y