第五节 - 归并排序
发布时间：2020-09-20 11:10来源：未知
第五节 归并排序
1、二路归并排序的思想
初始时将待排序序列R[1…n]看成是n个长度为1的有序序列，通过第一趟两两归并后，得到
个长度为2的有序序列，然后再两两归并，得到 
个长度为4的有序序列，如此重复，直到得到一个长度为n的有序序列。
2、实例分析
【例】已知序列（72，18，53，36，48，31，36），请写出对该序列采用二路归并排序方法进行升序排序时各趟的结果。
【解答】
3、算法描述（略）
4、算法分析
二路归并排序法需要进行 
趟，其时间复杂度为O（nlog2n），空间复杂度为O（n）。是一种稳定的排序方法。
