[低端筆記] MIT算法導論 3. Insertion Sort, Merge Sort

MIT的算法導論公開課有兩種版本, 我選較新版的
MIT 6.006 Introduction to Algorithms, Fall 2011

官方筆記

Why Sorting?

Insertion sort(10:00)

INSERTION-SORT (A, n) 
 for j ← 2 to n 
  將A[j]插入排序過的sub-array A[1:j-1]
   比較並swap

#Python

def insertion_sort(lst):
    for i in range(1, len(lst)):
        temp = lst[i]
        j = i - 1
        while j >= 0 and temp < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = temp
    return lst

Binary Insertion sort

Merge Sort (24:50)

採用divide and conquer

1. If n = 1, done (nothing to sort)
2. recursively sort A[ 1 . . n/2 ], A[ n/2+1 . . n ] 
3. 合併兩個排序完成的sub-arrays

#複雜度分析

各步驟複雜度

1. Θ(1)
2. 2T(n/2) 
3. Θ(n) 

T(n) = Θ(1) if n = 1;
       = 2T(n/2) + Θ(n) if n > 1
 → T(n) = Θ(n log n) by master theorem (課程用遞迴樹解)

空間複雜度