归并类

【思想】归并排序可以看作是分而治之的过程

1. 把无序序列分成好几个子序列，先对每个子序列单独处理
2. 之后将子序列进行归并

二路归并排序

思路

1. 将n个元素的无序序列分成n个序列，所以每个序列中只有一个元素
2. 每个序列两两归并，形成几个有序的二元组
3. 重复第二步，直到只剩下一个序列时，排序结果

【时间复杂度】整个时间复杂度为O(nlog2n)，归并的趟数为log2n

1. 归并排序中可选用merge()函数作为“归并操作”的基本操作，merge()的作用是将两个有序序列归并成一个整体有序的序列
2. 归并操作即为将待归并表中的元素复制到一个存储归并结果的表中的过程
3. 在顺序表中，merge()函数的归并操作执行次数为要归并的两个子序列中元素个数之和
4. 归并操作如下：
   • 第1趟归并需要执行2(n/2)=n次基本操作（其中2为两子序列元素个数之和，n/2为要归并的子序列对的个数；每个子序列对执行一次merge()函数，也就是2次基本操作）
   • 第2趟归并需要执行4(n/4)=n次基本操作
   • 第3趟归并需要执行8(n/8)=n次基本操作
   • 第k趟归并需要执行\(2^k * n/2^k = n\)次基本操作
   • 当\(n/2^k=1\)时，即需要归并两个子序列长度均为原序列的一般，只需要执行一次merge()函数归并排序即可结束。此时，k=log2n，即总共需要进行log2n趟排序，每趟排序执行n次基本操作
5. 整个归并排序总的基本操作执行次数为nlog2n，时间复杂度O(nlog2n)

【空间复杂度】归并排序需要转存整个待排序序列，因此空间复杂度为O(n)