マージソート at Python
組み込みのを使うのが普通なのだけど、まあ頭の体操がてら。
def mergesort(lst): if not isinstance(lst, list): raise ValueError("argument must be list") if len(lst) < 2: return lst lst1 = lst[:int(len(lst)/2)] lst2 = lst[int(len(lst)/2):] sorted_lst1 = mergesort(lst1) sorted_lst2 = mergesort(lst2) result = _merge(sorted_lst1, sorted_lst2) return result def _merge(lst1, lst2): result = [] total = len(lst1) + len(lst2) while len(result) < total: if len(lst1) == 0: result.extend(lst2) elif len(lst2) == 0: result.extend(lst1) elif lst1[0] < lst2[0]: result.append(lst1[0]) lst1.pop(0) else: result.append(lst2[0]) lst2.pop(0) return result
ソートにもいろいろあるけど、私はこのマージソートが一番好きですね。
半分こしていって最後に結合していくのがなんかいいかんじ。