为什么80%的码农都做不了架构师？>>> 
lecture 3 Insertion Sort, Merge Sort
1.(插入排序)Insertion sort
def InsertSort(L):
if(len(L) == 0 or len(L) == 1):
return L
tmp = 0
for i in range(1,len(L)):
for j in range(i,0,-1):
if L[j] < L[j - 1] :
tmp = L[j -1]
L[j - 1] = L[j]
L[j] = tmp
#print("swap:",str(L[j - 1]),str(L[j]))
#print(i,L)
return L2. (归并排序)Merge Sort
def MergeSort(L):
if(len(L) == 0 or len(L) == 1):
return L
iMid = len(L) // 2
LL = MergeSort(L[0: iMid])
RL = MergeSort(L[iMid : len(L)])
return Merge(LL, RL)
def Merge(LL,RL):
tmpL = []
ilLen = len(LL)
irLen = len(RL)
ilCount = 0
irCount = 0
while(ilCount < ilLen and irCount < irLen):
if(LL[ilCount] <= RL[irCount]):
tmpL.append(LL[ilCount])
ilCount = ilCount + 1
else :
tmpL.append(RL[irCount])
irCount = irCount + 1
if(ilCount != ilLen) :
while(ilCount < ilLen):
tmpL.append(LL[ilCount])
ilCount = ilCount + 1
if(irCount != irLen):
while(irCount < irLen):
tmpL.append(RL[irCount])
irCount = irCount + 1
return tmpL
3. 递归树(Recursion tree)
分析归并算法：
怎么计算出T(n)？使用递归树。
