merge sort

merge_sort.py

# coding: utf-8
# ソーティング練習のコード
# マージソート
import random
import unittest

LIMIT = 4

def insert_sort(inlist, begin, end):
    for i in xrange(begin + 1, end):
        tomove = inlist[i]
        j = i - 1
        while j >= begin and tomove < inlist[j]:
            inlist[j+1] = inlist[j]
            j -= 1
        inlist[j+1] = tomove
    return inlist

def merge_sort(inlist, begin, end):
    if end - begin <= LIMIT:
        return insert_sort(inlist, begin, end)
    middle = (end + begin) / 2
    merge_sort(inlist, begin, middle)
    merge_sort(inlist, middle, end)
    return _merge(inlist, (begin, middle, end))

def _merge(inlist, pos):
    begin, middle, end = pos
    left = inlist[begin:middle]
    right = inlist[middle:end]
    idx = begin
    while left or right:
        if not left:
            inlist[idx] = right.pop(0)
        elif not right:
            inlist[idx] = left.pop(0)
        else:
            if left[0] < right[0]:
                inlist[idx] = left.pop(0)
            else:
                inlist[idx] = right.pop(0)
        idx += 1
    return inlist

def isSorted(inlist):
    for i in xrange(len(inlist)-1):
        if inlist[i] > inlist[i+1]:
            return False
    return True

if __name__ == "__main__":
    testlist = range(10)
    random.shuffle(testlist)
    print testlist
    assert isSorted(testlist) == False
    sortedlist = merge_sort(testlist, 0, len(testlist))
    print sortedlist
    assert isSorted(sortedlist) == True