详解Java八大经典内排序算法——归并排序

      今天我们来介绍下一位朋友，归并排序！

      归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并排序是直接将两个有序的子表合并成一个有序的表即二路归并。

      将 Data[0..n-1] 看成是 n 个长度为 1 的有序序列，然后进行两两归并，得到 [n/2] 个长度为 2（最后一个有序序列的长度可能为 1）的有序序列，再进行两两归并，得到 [n/4] 个长度为 4（最后一个有序序列的长度可能小于 4）的有序序列，…… ，直到得到一个长度为 n 的有序序列。

※说明：归并排序每趟产生的有序区只是局部有序的，也就是说在最后一趟排序结束前，所有元素并不一定归位了。

      设待排序的表有 10 个元素，其关键字为 {18,2,20,34,12,32,6,16}。以下为归并排序的排序过程：

     采用二路归并排序时，需要进行 3 趟归并排序，其过程如图5.1所示。第 1 趟将每两个各含有一个元素的子表归并成一个新表，如将 {18} 和 {2} 排好序变为 {2,18}。第 2 趟将每两个各含有两个元素的子表归并成一个新表，如将 {2,18} 和 {20,34} 归并为{2,18,20,34}。  

      第 3 趟将每两个各含有 4 个元素的子表归并成一个新表，产生最终有序表。

▲ 二路归并排序过程