PHP規格とソートの実現について詳しく説明します。

正規化（Merge）順序付け法は、2つ（または2つ以上）の秩序表を新たな秩序表に結合することである。規格化された並べ替えの欠点は、メモリがデータアイテムの数に等しい他のサイズの配列を持つ必要があることである。初期配列がほぼメモリ全体を占めていると、規格化された順序付けは動作しないが、十分な空間があれば、規格化された順序付けは良い選択となる。
順序付けされているシーケンスを仮定します。
4 3 7 9 2 8 6
まず考え方を言います。並べ替えの中心思想は二つの並べ替えられたシーケンスを一つの順序に結合することです。
上のシーケンスは以下のように分割できます。
4 3 7 9
和
2  8  6
これらの2つのシーケンスは、それぞれ並べ替えられます。結果は以下の通りです。
シーケンスAに設定し、シーケンスBに設定します。
3 4 7 9
2  6  8
上の2つのシーケンスを並べ替えたものにマージします。
統合の具体的な考え方は：
2つの位置インジケータを設定して、それぞれシーケンスAとシーケンスBの開始位置を指します。赤いのはインジケータの位置です。
3 4 7 9
2  6  8
2つのインジケータが指している要素の値を比較して、小さなものを新しい配列に挿入します。例えば、シーケンスCのように、対応するインジケータを1つ後ろに移動します。
結果:
3 4 7 9
2  6  8
形成されたシーケンスC：要素が挿入されました。先ほどより小さい要素2.
2
シーケンスAとシーケンスBのインジケータが指す要素を再び比較します。小さいものをシーケンスCに入れて、対応するポインタを移動します。結果は以下の通りです。
3 4 7 9
2  6  8
2  3
これを類推して、シーケンスAまたはシーケンスBのいずれかのインジケータがすでに配列の端に移動しているまで、反復的に実行される。たとえば:
何度か比較した後、シーケンスBはインジケータをシーケンスの終端（最後の要素の後）に移動しました。
3 4 7 9
2  6  8
2 3 4 6 8
その後、使いきれなかったシーケンスをAの中の残りの要素を全部シーケンスCの後に挿入すればいいです。残りの9つはシーケンスCに挿入すればいいです。
シーケンスCの結果:
2 3 4 5 6 7 8 9
このようにして、2つの順序付けシーケンスを一つの順序付けシーケンスに統合する動作が実現され、
まず、このマージのphpコードを見ます。

/**
 *                 
 * @param $arrA,
 * @param $arrB,
 * @reutrn array      
 */
function mergeArray($arrA, $arrB) {
  $a_i = $b_i = 0;//          
  $a_len = count($arrA);
  $b_len = count($arrB);
  while($a_i<$a_len && $b_i<$b_len) {
    //   A   B      
    if($arrA[$a_i] < $arrB[$b_i]) {
      $arrC[] = $arrA[$a_i++];
    } else {
      $arrC[] = $arrB[$b_i++];
    }
  }
  //     A          ，           C   ：
  while($a_i < $a_len) {
    $arrC[] = $arrA[$a_i++];
  }
  //     B          ，           C   ：
  while($b_i < $b_len) {
    $arrC[] = $arrB[$b_i++];
  }
  return $arrC;
}

上の分析とプログラムの実現を経て、並べ替えられたシーケンスを統合する時間は線形であるべきで、つまりN-1回の比較が最大で発生します。ここで、Nはすべての要素の和です。
上記の説明により、2つの並べ替えされた配列を並べ替えるプロセスを実現しました。
この時、皆さんは疑問があるかもしれませんが、これはシーケンス全体とどういう関係がありますか？または、どのようにして最初の2つの並べ替えられたサブシーケンスを得ることができますか？
以下では、下記のようなものについて説明します。並べ替えとはどういう関係ですか？
私たちは次の配列を並べ替える必要があるとき、配列の前半部分と配列の後半部分をそれぞれ並べて並べ替えて、並べ替えの結果を統合してもいいですか？
例えば、並べ替え待ちの行列:
4 3 7 9 2 8 6
先に2つの部分に分けます
4 3 7 9
2 8 6
前半部分と後半部分をそれぞれ一つのシーケンスと見なして、再結合（分割、並べ替え、統合）動作を行う。
になります
前:
4 3
7 9
後:
2 8
  6
同じです  各シーケンスをまとめて並べ替え、再分割、並べ替え、統合します。
分割されたサブシーケンス内に1つの要素（長さは1）だけが存在する場合、このシーケンスはもはや分割する必要はなく、順序が良い配列である。このシーケンスを他のシーケンスと再結合すればいいです。最終的にはすべてを統合し、完全に並べ替えられた行列になります。
プログラムの実行:
上の説明を通して、再帰的なプログラムを使ってこのプログラムの設計を実現できると思います。
このプログラムを実現するには、次のような問題を解決する必要があります。
どのように配列を分割しますか？
二つのインジケータを設定し、一つのインジケータが開始されたと仮定すると、leftは、一つの指し示す配列の最後の要素である。right：
4 3 7 9 2 8 6
その後、$leftが$rightより小さいかどうかを判断し、このシーケンス内の要素の個数が一つより大きいと説明した場合、それを二つの配列に分割し、分割する方法は中間のインジケータを生成することであり、値はleft+$right/2で割り切れる。結果は：3、そして$leftから$センターを一つのグループに分けて、$center+1から$rightまでグループに分けます。
4 3 7 9
2 8 6
次に、再帰的には、$left、$center+1、$rightを利用して、それぞれ2つのシーケンスの左右のインジケータとして動作します。配列内に要素があることを知っています。left==米ドルright。上の連結配列に従ってください。

/**
* mergeSort     
*               
* @param &$arr array       
*/
function mergeSort(&$arr) {
  $len = count($arr);//      
 
  mSort($arr, 0, $len-1);
}
/**
*            
* @param &$arr array        
* @param $left int         
* @param $right int         
*/
function mSort(&$arr, $left, $right) {
 
  if($left < $right) {
    //          1    ，      ，    ，  
    //       ，  /2   
    $center = floor(($left+$right) / 2);
    //             ：
    mSort($arr, $left, $center);
    //             
    mSort($arr, $center+1, $right);
    //      
    mergeArray($arr, $left, $center, $right);
  }
}
 
/**
*                 
* @param &$arr,         
* @param $left,      A     
* @param $center,      A      B     ，     A     
* @param $right,      B     （   $center+1)
*/
function mergeArray(&$arr, $left, $center, $right) {
  //          
  $a_i = $left;
  $b_i = $center+1;
  while($a_i<=$center && $b_i<=$right) {
    //   A   B      
    if($arr[$a_i] < $arr[$b_i]) {
      $temp[] = $arr[$a_i++];
    } else {
      $temp[] = $arr[$b_i++];
    }
  }
  //     A          ，           C   ：
  while($a_i <= $center) {
    $temp[] = $arr[$a_i++];
  }
  //     B          ，           C   ：
  while($b_i <= $right) {
    $temp[] = $arr[$b_i++];
  }
 
  // $arrC       ，   $arr ：
  for($i=0, $len=count($temp); $i<$len; $i++) {
    $arr[$left+$i] = $temp[$i];
  }
 
}
 //do some test:
$arr = array(4, 7, 6, 3, 9, 5, 8);
mergeSort($arr);
print_r($arr);

上のコードバンドの順序付けの配列は、引用伝達を使用し、スペースを節約するために使用されます。
また、その中の統合配列の方式も、空間を節約するために相対的に修正され、すべての操作をドルarrに置いて完了し、資源の節約を伝えます。
上のコードが整理されました。規格化された時間の複雑さはO（N＊LogN）効率ですか？それともかなり客観的です。
また、アルゴリズムを並べ替えて、中心思想は複雑な問題を似たような小さな問題に分解し、小さい問題をすぐに解決できるまで分解して、分解した結果を再結合する方法です。この思想は成語でゼロになると形容されている。コンピュータ科学において、分治策という専門があります。大きな問題が小さくなった問題は小さい結果をまとめて大きな結果になります。
分割戦略は多くのお笑いアルゴリズムの基礎であり、我々は迅速な並べ替えを議論する時にも、分割戦略を使用します。
最後にこのアルゴリズムを簡単に説明します。このアルゴリズムは時間の複雑さにおいてO（NLogN）に達していますが。しかし、まだ小さな問題があります。つまり、2つの配列を統合する時、配列の総要素の個数がNなら、同じ大きさの空間をもう一つ開けて、統合時のデータを保存する必要があります。また、データを$tempコピーする必要があります。だから、いくつかの資源を浪費します。したがって、実際の並べ替えでは比較的少ない使用です。