[硕.Love Python] MergeSort(归并排序)

zzgzyyz

　　
def merge(s, d, i, m, n):
　　
    # merge [i, m) [m, n)
　　
    j, k = m, i
　　

　　
    while i < m and j < n:
　　
        if s < s[j]:
　　
            d[k] = s
　　
            i += 1
　　
        else:
　　
            d[k] = s[j]
　　
            j += 1
　　
        k += 1
　　

　　
    while i < m:
　　
        d[k] = s
　　
        i += 1
　　
        k += 1
　　

　　
    while j < n:
　　
        d[k] = s[j]
　　
        j += 1
　　
        k += 1
　　

　　
def mergeOnePass(s, d, mlen):
　　
    i, n = 0, len(s)
　　
    while i + 2 * mlen <= n:
　　
        merge(s, d, i, i + mlen, i + 2 * mlen)
　　
        i += 2 * mlen
　　

　　
    if i + mlen < n:
　　
        merge(s, d, i, i + mlen, n)
　　
    else:
　　
        for i in xrange(i, n):
　　
            d = s
　　

　　
def mergeSort(s):
　　
    tmp = s[:]
　　

　　
    mlen, n = 1, len(s)
　　
    while mlen < n:
　　
        mergeOnePass(s, tmp, mlen)
　　
        mlen *= 2
　　
        mergeOnePass(tmp, s, mlen)
　　
        mlen *= 2
　　

　　
if __name__ == '__main__':
　　
    from random import shuffle
　　
    s = range(100)
　　
    shuffle(s)
　　
    print s
　　
    mergeSort(s)
　　
    print s