Question

二路归并排序是什么？

Answer 1

二路归并排序是：假设初始序列中含有N个记录，则可以看成N个有序的子序列，每个子序列的长度为一，然后两两归并，得到［N/2]（表示不小于N/2的最小整数）个长度为2或者1的有序子序列：再两两归并，如此重复，直到得到一个长度为N的有序子序列为止，称为2路归并排序（Merge Sort)。

归并排序的步骤

1、将给定的序列，从中间分成两个子序列，然后再将子序列以同样的方式拆分子序列，直到子序列长度为1，也就是称为有序序列。

2、申请额外的空间，为两个子序列长度和，用于存放合并后的序列。然后设定两个指针分别指向两个有序子序列的起始位置，然后比较两个指针指向元素的大小，将较小的元素放入合并空间，并移动指向该元素的指针，另外一个子序列的指针不变，然后继续比较两个指针指向元素的大小，直到两个有序子序列中的值全部放入合并空间中。

3、自下而上的合并所有的子序列，直到合并完所有的子序列之后，合并空间中的序列即为有序序列。