[硕.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

刘硕老师Python精品课程：

《Python高级编程技巧实战》：

http://coding.imooc.com/class/62.html

《Python算法实战视频课程》：

http://study.163.com/course/courseMain.htm?courseId=1003617013

《Python科学计算—NumPy实战课程》：

http://edu.51cto.com/course/course_id-5046.html

熊猫TV直播间：

http://www.panda.tv/671023

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

原文：http://liushuo777.blog.51cto.com/10091950/1895914