def compare_and_swap(x, a, b):
if x[a] > x[b]:
x[a], x[b] = x[b], x[a]
def oddeven_merge(x, lo, hi, r):
step = r * 2
if step < hi - lo:
oddeven_merge(x, lo, hi, step)
oddeven_merge(x, lo + r, hi, step)
for i in range(lo + r, hi - r, step):
compare_and_swap(x, i, i + r)
else:
compare_and_swap(x, lo, lo + r)
def oddeven_merge_sort_range(x, lo, hi):
""" 区間lo と hiのソートを行う。
注意: 端点 (lo と hi) は含むものとする。
"""
if (hi - lo) >= 1:
# ひとつ以上の要素があった場合、入力を
# 長さの半分で前後に分割し、
# その後それぞれをマージソートする。
mid = lo + ((hi - lo) / 2)
oddeven_merge_sort_range(x, lo, mid)
oddeven_merge_sort_range(x, mid + 1, hi)
oddeven_merge(x, lo, hi, 1)
def oddeven_merge_sort(x):
oddeven_merge_sort_range(x, 0, len(x)-1)
>>> data = [2, 4, 3, 5, 6, 1, 7, 8]
>>> oddeven_merge_sort(data)
>>> data
[1, 2, 3, 4, 5, 6, 7, 8]