Detailed explanation of merge sort of PHP sorting algorithm series

This article explains the detailed explanation of merge sorting in the PHP sorting algorithm series.

MERGE SORT

Merge sort (MERGE-SORT) is an effective sorting algorithm based on the merge operation. This algorithm is a very effective sorting algorithm that uses the divide and conquer method. Typical applications. Merge the already ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a two-way merge.

Merge process

The core of merge sort is how to merge two ordered sequences. Assume there are two ordered arrays. Compare the first elements of the two ordered arrays, which one is smaller? Just take whoever you want and put the element into the third array. After taking it, the element will be deleted in the corresponding array, and so on. When you get an array that has no elements, you can add the remaining elements of the other array. Elements are added directly to the third array.

Principle

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

2. Merge the above sequences again to form ceil(n/4) sequences. Each sequence contains four elements, and the last sequence may have only three or less elements.

3. Repeat step 2 until all elements are sorted.

Example

Sort the 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 merge

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

After the third merger

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

After the fourth merge

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

PHP code implementation

function merge_sort($arr){
 
$length=count($arr);
 
if($length<=1){
 
return $arr;
 
}
 
//分解数组，递归排序
 
$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);
 
}

This article explains the detailed explanation of merge sort in the PHP sorting algorithm series. Please pay attention to the PHP Chinese website for related content.

Related recommendations:

thinkPHP5 framework database coherent operation: cache() usage details

##PHP interface multiple inheritance and tarits Tutorial details on how to achieve multiple inheritance effects

PHP Tutorial on how to get the start date and end date of the first week of a certain year

The above is the detailed content of Detailed explanation of merge sort of PHP sorting algorithm series. For more information, please follow other related articles on the PHP Chinese website!