假设有一个待排序的数组$arr = [4, 2, 8, 5, 1, 3, 7, 6]。我们希望将这个数组按照从小到大的顺序进行排序。现在我们来看看如何使用非递归的方式实现归并排序。
首先，我们将原始数组分割成多个子数组，并依次以长度为1的子数组开始进行合并。代码如下：
//by www.qzphp.cn
function mergeSort($arr) {
$len = count($arr);
$step = 1;
while ($step < $len) {
$start = 0;
while ($start < $len) {
$mid = $start + $step;
$end = min($start + 2 * $step, $len);
merge($arr, $start, $mid, $end);
$start += 2 * $step;
}
$step *= 2;
}
return $arr;
}
function merge(&$arr, $start, $mid, $end) {
$tmp = [];
$i = $start;
$j = $mid;
while ($i < $mid && $j < $end) {
if ($arr[$i] < $arr[$j]) {
$tmp[] = $arr[$i++];
}
else {
$tmp[] = $arr[$j++];
}
}
while ($i < $mid) {
$tmp[] = $arr[$i++];
}
while ($j < $end) {
$tmp[] = $arr[$j++];
}
for ($k = 0;
$k < $end - $start;
$k++) {
$arr[$start + $k] = $tmp[$k];
}
}
上述代码中的
mergeSort函数负责驱动整个排序过程。首先，我们需要获取待排序数组的长度$len，然后设置初始步长$step为1。接下来的while循环用于控制每一次合并的子数组长度，从1开始直到不小于待排序数组长度为止。在内层的while循环中，我们通过设置$start和$end指针来确定当前要合并的两个子数组的位置。然后，调用
merge函数来对这两个子数组进行合并排序。merge函数中的$tmp数组用于保存已经排好序的子数组，$i和$j分别代表两个子数组的起始位置。在while循环中，我们通过逐一比较两个子数组的元素大小，将较小的元素放入$tmp数组中，并移动相应的指针。最后，将$tmp数组中的元素复制回原数组$arr，完成合并排序。在最外层的while循环结束后，$step的值会大于待排序数组的长度，这时整个排序过程就完成了，我们可以直接返回排好序的数组$arr。
//by www.qzphp.cn
$arr = [4, 2, 8, 5, 1, 3, 7, 6];
$result = mergeSort($arr);
echo implode(', ', $result);
// 输出：1, 2, 3, 4, 5, 6, 7, 8</
pre>
通过上述代码，我们可以得到排好序的数组[1, 2, 3, 4, 5, 6, 7, 8]。这就是使用非递归的方式实现归并排序的结果。
总结起来，非递归的归并排序算法的基本思想是分割待排序的数组为若干个子数组，然后逐一合并子数组，直到最后得到一个完整的有序数组。在PHP中，我们可以通过设置步长和指针的方式来控制子数组的范围，并使用一个辅助数组来保存已经排好序的子数组。这种非递归方式实现的归并排序算法在处理大规模数据时具有较好的性能表现。
