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 += 1def 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 *= 2if __name__ == '__main__': from random import shuffle s = range(100) shuffle(s) PRint s mergeSort(s)
