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