<?php
/**
* 并归排序
* 思想:将数据排序,一个小的,一个大的,这样遍历数据得时候,这样第一次遍历得时候可以得到一个(小,大),(小,大)数组
* 然后通过递归合并,(小1,大1),(小2,大2)每次取出2个数组的第一个数,比较,哪个小,放到一个新的数据tmp里面,然后小的数组current指针后移,继续比较,如果大1<小2,将大1放到
* tmp里面,然后将剩余的小2,大2依次放入数组,就是两个数组合并排序完了,即tmp = array(小1,大1,小2,大2)
*
* 如果刚才大1>小2,则先放入小2,然后(小2,大2)的数组current后移,然后比较大1和大2,如果大1>大2,则大2先放入tmp数组,剩下的大1,放入数组,就是(小1,小2,大2,大1)升序的排好数组
*/
//测试类
class MergeTest
{
private $data;
public function __construct($data)
{
$this->init($data);
}

//执行
public function run()
{
$this->merge();
print_r($this->data);
}
//初始化并归数组,相邻两个元素合并为一个数组(小的在前面)
private function init($data)
{
$tmp = [];
$num = count($data);
if ($num % 2 == 0) {
$items = $num / 2;
} else {
$items = ($num 1) / 2;
}

for ($i = 0; $i < $items; $i++) {
if ($data[2 * $i] < $data[2 * $i + 1]) {
array_push($tmp, [$data[2 * $i], $data[2 * $i + 1]]);
} else {
array_push($tmp, [$data[2 * $i + 1], $data[2 * $i]]);
}

}
if ($num % 2 != 0) {
array_push($tmp, [$data[$num 1]]);
}

$this->data = $tmp;
}

//并归递归调用
private function merge()
{
$re = [];
$size = count($this->data);
if ($size != 1) //没有完成并归,继续
{
for ($i = 0; $i < $size 1; $i += 2) {
$re[] = $this->doubleMerge($this->data[$i], $this->data[$i + 1]);
}

if ($size % 2 != 0) {
$re[] = $this->data[$size 1];
}

$this->data = $re;
$this->merge();
}
}

//合并两个有序序列
private function doubleMerge($a, $b)
{
$re = [];
$i = $j = 0;
$s1 = count($a);
$s2 = count($b);

while (true) {
if ($a[$i] <= $b[$j]) {
array_push($re, $a[$i]);
$i++;
} else {
array_push($re, $b[$j]);
$j++;
}

if ($i == $s1) {
return array_merge($re, array_slice($b, $j));
}

if ($j == $s2) {
return array_merge($re, array_slice($a, $i));
}

}

}
}

$a = new MergeTest([3,8,8,19, 1, 9, 2, 7, 6, 11,19, 5, 4, 13]);
$a->run();