常见排序算法7——归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。

算法描述

1）将原始序列从中间分为左、右两个子序列，此时序列数为2

2）将左序列和右序列再分别从中间分为左、右两个子序列，此时序列数为3）重复以上步骤，直到每个子序列都只有一个元素，可认为每一个子序列都是有序的

4）最后依次进行归并操作，直到序列数变为1

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

代码实现

PHP代码

算法复杂度

时间复杂度：O(nlogn)

空间复杂度：O(n)

算法稳定性

归并排序是稳定的排序算法