讀處

著名的排序演算法Merge-Sort採取divide-and-counquer策略

divide-and-counquer主要分成三個步驟進行

1.Divide: 將原問題分成若干個子問題

2.Conquer: 遞迴解各個子問題，當子問題的size夠小時直接解(遞迴到初始條件)

3.Combine: 將子問題的解合併成原問題的解

而Merge-Sort採取divide-and-counquer策略的步驟如下

1.Data list 一列切割成兩等分

2.左右sublist各自sort in merge sort

3.合併左右半部兩個runs成一個run

註:run是指已排序好的片段串列

Psudocode

Program(C++)

Time complexity of Merge-Sort: 

假設在輸入大小為n的陣列時所需時間為T(n)

則將list切割左右兩半部的sorting time皆為T(n/2)

合併Merge所需時間為O(n)

遞迴式為

T(n)=2T(n/2)+O(n),T(1)=O(1)

利用master theorem分析得T(n)=O(nlogn)