merge_sort.py

# encoding:utf-8


def mergesort(arr):
    length = len(arr)
    if length <= 1: return arr
    middle = length // 2
    start = mergesort(arr[:middle])
    end = mergesort(arr[middle:])
    return merge2(start, end)


def merge(arr1, arr2):
    arr = []
    length = len(arr1) + len(arr2)

    i, j = 0, 0
    while length:
        if j == len(arr2):
            arr.extend(arr1[i:])
            break

        if i == len(arr1):
            arr.extend(arr2[j:])
            break

        if arr1[i] < arr2[j]:
            arr.append(arr1[i])
            i += 1
        else:
            arr.append(arr2[j])
            j += 1

        length -= 1
    return arr


def merge2(arr1, arr2):
    arr = []
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            arr.append(arr1[i])
            i += 1
        else:
            arr.append(arr2[j])
            j += 1
    if arr1[i:]: arr.extend(arr1[i:])
    if arr2[j:]: arr.extend(arr2[j:])
    return arr


if __name__ == '__main__':
    from random import randint
    n = [randint(0, 100) for x in range(20)]
    print n, '#' * 10
    print mergesort(n)