root/python/exercise/mergesort2.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以下なら、そのまま返す。
    # リストじゃない場合のためにリストに変換。
    return list(arg)

  # [1, 2, 3] ==> [[1], [2], [3]]
  sorting = [[x] for x in arg]

  # [[1, 2, 3]]という形になるまで繰り返す。
  while len(sorting) > 1:

    # リストの長さの半分（端数は切り下げ）まで繰り返す。
    # 端数が出た場合には右端の1個が処理されないが気にしない。
    for offset in xrange(len(sorting) / 2):

      # 着目点offsetから2個を取り出して、
      a = sorting[offset]
      b = sorting[offset + 1]

      # マージする。
      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))

      # 取り出した2個の部分を、マージされた物で置き換える。
      sorting[offset:offset+2] = [r + a + b]

  return sorting[0]


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