• Merge Sort
• Master Theorem
• Divide-and conquer paradigm
• Other algorithms by D&C

合并排序 Merge Sort

合并排序A[1..n]

1. 如果n=1，则完成。
2. 对A[1..n/2]和A[n/2+1..n]进行递归排序
3. “合并”2个已排序列表。

Merge（）获取A的两个已排序子数组，并将它们合并为A的单个已排序子数组（这需要多长时间？）

MERGE(A, p, q, r)

合并排序分析 Analysis of Merge Sort

复发 Recurrences

• 表达方式： 这是一种重复递推：用较小函数的值来描述函数的方程

合并排序算法的结构 Structure of merge sort algorithm

1. 将问题分解为类似的（较小的）子问题
2. 递归求解子问题
3. 结合解决方案得出最终答案

合并排序示例 Example of Merge Sort

分而治之范式 Divide-and-conquer paradigm

1. 把问题分成子问题。
2. 通过递归求解来克服子问题。
3. 组合子问题解决方案。

D&C范例 Example of D&C Paradigm

合并排序作为分治算法

1. 分：将n个阵列划分为两个n/2子阵列。
2. 征服：对两个子数组进行递归排序。
3. 合并：线性时间合并。

合并排序的递归 Recurrence for Merge sort

一个有用的递推关系 A Useful Recurrence Relation

•合并排序重复。

•解决方案。。

•各种各样的证据。我们描述了几种证明这种复发的方法。最初我们假设n是2的幂

替换≤带=。

递归树证明 Proof by Recursion Tree

伸缩校样 Proof by Telescoping

归纳法证明 Proof by Induction

有简单的方法吗？