归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型的应用。它的基本操作是：将已有的子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

1.分解—-将序列每次折半拆分
2.合并—-将划分后的序列段两两排序合并

归并排序

合并思路
设置为序列A，与序列B，
3 4 7 9
2 6 8
设置两个位置指示器，分别指向序列A与序列B开始的位置：红色为指示器指向位置：

3 4 7 9

2 6 8

形成的序列C：已经被插入一个元素了，刚才较小的元素2.
2
然后再次比较序列A与序列B中指示器所指向的元素：将小的放入到序列C中，移动相应指针，结果为：

3 4 7 9

2 6 8

2 3
以此类推，迭代执行，直到序列A或者序列B中某个指示器已经移到到数组末端。
2 3 4 6 7 8

java

public static void merge(int[] array, int low, int middle, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;
    int j = middle + 1;
    int k = 0;
    while (i <= middle && j <= high) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    while (i <= middle) {
        temp[k++] = array[i++];
    }
    while (j <= high) {
        temp[k++] = array[j++];
    }
    for (int m = 0; m < temp.length; m++) {
        array[m + low] = temp[m];
    }
}

php

function mergeSort(&$arr, $low, $high) {
    if ($low < $high) {
        $mid = intval(($low + $high) / 2);
        mergeSort($arr, $low, $mid);
        mergeSort($arr, $mid + 1, $high);
        merge($arr, $low, $high, $mid);
    }
}
//归并排序
function merge(&$arr, $low, $high, $mid) {
    $minLow = $low;
    $maxHigh = $mid + 1;
    while ($minLow <= $mid && $maxHigh <= $high) {
        if ($arr[$minLow] <= $arr[$maxHigh]) {
            $temp[] = $arr[$minLow];
            $minLow++;
        } else {
            $temp[] = $arr[$maxHigh];
            $maxHigh++;
        }
    }
    while ($minLow <= $mid) {
        $temp[] = $arr[$minLow++];
    }
    while ($maxHigh <= $high) {
        $temp[] = $arr[$maxHigh++];
    }
    $length = count($temp);
    for ($i = 0; $i < $length; $i++) {
        $arr[$i + $low] = $temp[$i];
    }
}