Stanford Algorithm 1.5-1.7レコード

Merge Sort
この課程の前のいくつかの授業は入門として、いくつかのアルゴリズムを紹介するが、後にはより堅固で、複雑度分析などの下位層がある.
話者によると、このアルゴリズムは実際に広く引用されているが、私は後で少しgoogleして、このアルゴリズムの最悪の最良の状況は同じ時間の複雑さだと言った.
思想はとても簡単で、Divide and Conquerに属して、再帰的にそれを二分して散らして、更にO(N)の関数でそれらをmergeします.次のコードは、重複する数字がまだ含まれているということではありません.

def merge_sorted_lists(a, b):
    res = []
    # init indices for a, b
    i = 0
    j = 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            res.append(a[i])
            i = i + 1
        else:
            res.append(b[j])
            j = j + 1
    if i < len(a):
        res = res + a[i:]
    else:
        res = res + b[j:]
    return res

def merge_sort(l):
    # THIS IS for exit!!!
    if len(l) <= 1:
        return l
    a = l[:int(len(l)/2)]
    b = l[int(len(l)/2):]
    left = merge_sort(a)
    right = merge_sort(b)
    return merge_sorted_lists(left, right)
    
if __name__ == '__main__':
    l = [4,5,7,9,7,5,1,0,7,-2,3,-99,6]
    print(merge_sort(l))

その複雑さを測定する時、話し手はrecursive treeを採用して、実は愚かな方法で、再帰過程をすべて列挙して、各階層の必要な代価を計算します.第j(j=0,1,2,...,logn)層には、2^jのサブ問題(すなわちmergeが必要である)があり、各サブ問題のsizeは(せいぜい)6(N/(2^j))を必要とする代価(コード行数)である.したがって、どの層においても対価は6 Nであるため、最大6 N(1+logn)となる.