https://www.yduba.com/biancheng-9902519493.html
    归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序有，称为二路归并。
    归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

    算法步骤
    1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
    2. 设定两个指针（即数组下标），最初位置分别为两个已经排序序列的起始位置；
    3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到一下位置；
    4. 重复步骤3直到某一指针达到序列尾；
    5. 将另一序列剩下的所有元素直接复制到合并序列尾。

    效率分析
    归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(n * logn)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N * logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

    算法稳定性
    归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

    动图演示
    5归并排序 - 图1

    代码实现

    1. <?php
    2. function mergeSort(array $numbers=array()) 
    3. {
    4.     $count = count( $numbers );
    5.     if( $count <= 1 ) return $numbers;
    7.     // 将数组分成两份 $half = ceil( $count / 2 );
    8.     $half  = ($count >> 1) + ($count & 1);
    9.     $arr2d = array_chunk($numbers, $half);
    11.     $left  = mergeSort($arr2d[0]);
    12.     $right = mergeSort($arr2d[1]);
    14.     while (count($left) && count($right))
    15.     {
    16.         if ($left[0] < $right[0])
    17.             $reg[] = array_shift($left);
    18.         else
    19.             $reg[] = array_shift($right);
    20.     }
    21.     return array_merge($reg, $left, $right);
    22. }