root/python/exercise/mergesort.py

#!/usr/bin/python
# coding:utf-8

'''マージソート
練習問題「マージソートを作る」。

>>> mergeSort((3, 1, 100, 5, 8, 4, 3, 9, 2, 0, 7, 10))
[0, 1, 2, 3, 3, 4, 5, 7, 8, 9, 10, 100]
>>> mergeSort(())
[]
>>> mergeSort((3,))
[3]
>>> mergeSort((4,3))
[3, 4]
>>> mergeSort([7,6])
[6, 7]
'''

def mergeSort(arg):
  '''マージソート
  タプルまたはリストを与える。
  リストを返す。
  '''
  if len(arg) < 2:
    # 項目数が1以下なら、そのまま返す。0にはならないけど。
    # リストじゃない場合のためにリストに変換。
    return list(arg)

  # 真ん中付近で2つに分離して、それぞれソートする。再帰呼び出し。
  n = len(arg) / 2
  (a, b) = (mergeSort(arg[:n]), mergeSort(arg[n:]))

  # マージする。
  # aまたはbのいずれかの項目数がゼロになるまで、
  # 先頭の値のうち小さい方をpopして、rに付け加える。
  r = []
  while len(a) > 0 and len(b) > 0:
    if a[0] < b[0]:
      r.append(a.pop(0))
    else:
      r.append(b.pop(0))

  # aまたはbのいずれかの項目数がゼロになったら、あとは足し合わせるだけ。
  return r + a + b


# テスト用。
if __name__ == '__main__':
  import doctest
  doctest.testmod()