Detailed Explanation of Merging Sorting of PHP Sorting Algorithm Series

Merging sort

Merge sort (MERGE-SORT) is an effective sort algorithm based on merge operation, which is a typical application of divide-and-conquer method (Divide and Conquer). Combining the ordered sub-sequences to obtain a completely ordered sequence; That is to say, each sub-sequence is ordered first, and then the sub-sequence segments are ordered. If two ordered tables are merged into one ordered table, it is called two-way merging.

Merging process

The core of merge sorting is how to merge two ordered sequences, Assuming there are two ordered arrays, compare the first element of the two ordered arrays, take whoever is smaller, and put the element into the third array. After taking it, this element will be deleted in the corresponding array, and so on. When one array has no elements, the remaining elements of the other array can be directly added to the third array.

Principle

1. Merge every two adjacent numbers of the sequence to form ceil (n/2) sequences. After sorting, each sequence contains two elements, and the last sequence may only have one element.

2. The above sequences are merged again to form ceil (n/4) sequences, each of which contains 4 elements, and the last sequence may only have 3 or less elements.

3. Repeat step 2 until all elements are sorted.

Example

Sort Array [53, 89, 12, 6, 98, 25, 37, 92, 5]

After the first merge,

(53, 89), 12, (6, 98), (25, 37), (5, 92)

After the second merging,

(12,53,89),(6,25,37,98),(5,92)

After the third merging,

(6,12,25,37,53,89,98),(5,92)

After the fourth merging,

5,6,12,25,37,53,89,92,98

PHP code implementation

<?php
function merge_sort($arr){
  $length=count($arr);
  if($length<=1){
    return $arr;
  }
  // Decompose arrays and sort recursively 
  $half=ceil($length/2);
  $arr2=array_chunk($arr,$half);
  $left=merge_sort($arr2[0]);
  $right=merge_sort($arr2[1]);
  while(count($left)&&count($right)){
    if($left[0]<$right[0]){
      $reg[]=array_shift($left);
    }else{
      $reg[]=array_shift($right);
    }
  }
  return array_merge($reg,$left,$right);
}