数据结构和算法——合并排序

1、要解决的问题

给定如下所示的数字列表，请按升序对它们进行排序。

要求

对数字进行排序时，需要使用插入。

用PHP实现该算法

2、伪代码说明

合并排序是一种分而治之的算法。它的工作方式是将列表连续分成两半，直到两半都被排序，然后执行操作合并将两个列表组合成一个排序的新列表。

拆分列表时，如果列表包含零个或一个元素，我们认为该列表已排序。

拆分：

合并：

描述合并排序的伪代码如下：

3、PHP实现合并排序

我们可以看到，该算法有两个过程。这导致我们需要两个PHP函数，其中第一个函数（）涉及递归。

我们严格遵循伪代码并用PHP实现该算法。我们要强调的唯一部分是几个内置的PHP数组函数：

：提取数组的一个切片。当我们想要数组的某个部分时，此函数非常方便。

：从数组的开头删除一个元素。当我们要删除数组的第一个元素时，此函数非常方便。