2、归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide
and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

[平均算法复杂度：O(n*log〈2〉n)]

应用场景分析：归并排序和冒泡排序类似，也是稳定性比较好的一种排序算法，应用场景同样也和冒泡排序类似。不同之处在于归并算法在对大数据量进行排序时，效率会明显高于冒泡排序，这点可通过对数函数曲线n*log〈2〉n与n*n的函数曲线中明显的观察到：

<?php
// 归并排序：
// 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
//执行时间 3.3000000000005E-5 微秒
function Merge(&$arr, $left, $mid, $right) { 
  $i = $left; 
  $j = $mid + 1; 
  $k = 0; 
  $temp = array(); 
  while ($i <= $mid && $j <= $right) 
  { 
    if ($arr[$i] <= $arr[$j]) 
      $temp[$k++] = $arr[$i++]; 
    else 
      $temp[$k++] = $arr[$j++]; 
  } 
  while ($i <= $mid) 
    $temp[$k++] = $arr[$i++]; 
  while ($j <= $right) 
    $temp[$k++] = $arr[$j++]; 
  for ($i = $left, $j = 0; $i <= $right; $i++, $j++) 
    $arr[$i] = $temp[$j]; 

    return $arr; 
}
function MergeSort(&$arr, $left, $right) 
{ 
  if ($left < $right) 
  { 
    $mid = floor(($left + $right) / 2); 
    MergeSort($arr, $left, $mid); 
    MergeSort($arr, $mid + 1, $right); 
    Merge($arr, $left, $mid, $right); 
  } 
  return $arr;
}

$arr = ['12','65','20','22','32','52','3'];

// 记录开始时间
$time_start = microtime();

$res = MergeSort($arr,0,6);

echo "<pre>";
print_r($res);
echo "</pre>";

// 记录结束时间
$time_end = microtime();
$time = $time_end - $time_start;
 // 输出运行总时间 
echo "执行时间 $time 微秒";
?>