本文主要介绍了php归并排序的实现算法，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。有兴趣的朋友可以来了解一下。
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表。归并排序的一个缺点是它需要存储器有另一个大小等于数据项数目的数组。如果初始数组几乎占满整个存储器，那么归并排序将不能工作，但是如果有足够的空间，归并排序会是一个很好的选择。
假设待排序的序列：
4 3 7 9 2 8 6
先说思路，归并排序的中心思想是将两个已经排序好的序列，合并成一个排序的序列。
上面的序列可以分成：
4 3 7 9
和
2 8 6
这两个序列，然后对这两个序列分别排序：结果为：
设置为序列A，与序列B，
3 4 7 9
搞gaodaima代码
2 6 8
将上面的两个序列 合并成一个排序好的序列：
合并的具体思路是：
设置两个位置指示器，分别指向序列A与序列B开始的位置：红色为指示器指向位置：
3 4 7 9
2 6 8
比较两个指示器所指向的元素的值，将较小的插入到一个新的数组内，例如序列C，同时将对应的指示器向后移动一位：
结果为：
3 4 7 9
2 6 8
形成的序列C：已经被插入一个元素了，刚才较小的 元素2.
2
然后 再次 比较序列A与序列B中指示器所指向的元素：将小的放入到序列C中，移动相应指针，结果为：
3 4 7 9
2 6 8
2 3
以此类推，迭代执行，直到序列A或者序列B中某个指示器已经移到到数组末端。例如：
多次比较后，序列B已经将指示器移出到序列末端（最后一个元素之后）了。
3 4 7 9
2 6 8
2 3 4 6 7 8
然后将没有用完的序列，这里面是序列A中其余的元素全部插入到序列C的后边即可，就剩下一个9 了，将其插入到序列C后即可：
序列C结果：
2 3 4 5 6 7 8 9
这样就实现了将两个有序序列合并成一个有序序列的操作，
下面先看这个合并的php代码：
/** * 将两个有序数组合并成一个有序数组 * @param $arrA, * @param $arrB, * @reutrn array合并好的数组 */function mergeArray($arrA, $arrB) { $a_i = $b_i = 0;//设置两个起始位置标记 $a_len = count($arrA); $b_len = count($arrB); while($a_i<$a_len && $b_i<$b_len) { //当数组A和数组B都没有越界时 if($arrA[$a_i] < $arrB[$b_i]) { $arrC[] = $arrA[$a_i++]; } else { $arrC[] = $arrB[$b_i++]; } } //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内： while($a_i < $a_len) { $arrC[] = $arrA[$a_i++]; } //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内： while($b_i < $b_len) { $arrC[] = $arrB[$b_i++]; } return $arrC;}
经过上面的分析和程序的实现，我们不难发现，合并已排序的序列的时间应该是线性的，就是说，最多会发生N-1次比较，其中N是所有元素之和。
通过上面的描述，我们实现了将两个排序好的数组进行和并的过程。
此时，大家可能会有疑问，这个和归并排序整个序列有什么关系？或者你是如何能够得到最开始的两个排序好的子序列的呢？
下面，我们就来描述以下什么是归并排序，然后再看，上面的合并与归并排序的关系是如何的：
转载请注明原文链接：PHP实现归并排序的方法
