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

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

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

    while i < m:
 d[k] = s[i]
 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[i] = s[i]

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