插入排序

最好情况输入数组开始时候就是满足要求的排好序的，时间代价为θ(n)；

最坏情况输入数组是按逆序排序的，时间代价为θ(n^2)。

归并排序

归并排序采用了算法设计中的分治法，分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题，递归的解决这些子问题，然后再去合并其结果，得到原问题的解。

分治模式在每一层递归上有三个步骤：

分解（divide）：将原问题分解成一系列子问题。

解决（conquer）：递归地解答各子问题，若子问题足够小，则直接求解。

合并（combine）：将子问题的结果合并成原问题的解。

归并排序（merge sort）算法按照分治模式，操作如下：

分解：将n个元素分解成各含n/2个元素的子序列

解决：用合并排序法对两个序列递归地排序

合并：合并两个已排序的子序列以得到排序结果

算法中含有对其自身的递归调用，其运行时间可以用一个递归方程（或递归式）来表示。归并排序算法分析采用递归树进行，递归树的层数为lgn+1，每一层的时间代价是cn，整棵树的代价是cn(lgn+1)=cnlgn+cn，忽略低阶和常量c，得到结果为θ(nlg n)。