归并排序 递归 非递归

import sys

def merge(a, b, l, m, r):
    i = l
    k = l
    j = m + 1
    while i <= m and j <= r:
        if a[i] <= a[j]:
            b[k] = a[i]
            i += 1
        else:
            b[k] = a[j]
            j += 1
        k += 1
    if i > m:
        while j<=r:
            b[k] = a[j]
            k += 1
            j += 1
    if j > r:
        while i<=m:
            b[k] = a[i]
            k += 1
            i += 1
    #copy to a
    i = l
    while i<= r:
        a[i] = b[i]
        i += 1   
    pass

def mergeSort(a, l, r):
    if l>=r:
        return
    m = (l+r)/2
    mergeSort(a,l,m)
    mergeSort(a,m+1,r)   
    merge(a,b,l,m,r)

def mergeSort2(a, n):
    s = 2
    while s < n:
        i = 0
        while i <= n - 2*s:
            merge(a,b, i, i+s-1, i+2*s-1)
            i += 2*s
        s += s

if __name__ == '__main__':
   
    a = [3, 5, 6, 10, 2, 7, 4, 20, 1, 100, 99 ,45, 60]
    length = len(a)
    b = [0] * length   
   
    try:
        mergeSort(a, 0, length-1)
        mergeSort2(a, length-1)
    except Exception,e:
        print e
    print a