Detailed explanation of merge sort of PHP sorting algorithm

There are many kinds of php sorting algorithms. This article mainly introduces the relevant information of the PHP sorting algorithm series merge sorting in detail. It has certain reference value. Interested friends can refer to it. I hope it can help everyone.

Merge sort

Merge sort (MERGE-SORT) is an effective sorting algorithm based on merge operations. The algorithm uses the divide and conquer method (pide and Conquer) is a very typical application. 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 that there are two ordered arrays and compare the two ordered arrays. Take the first element, whichever is smaller, and put the element into the third array. After taking it, the element will be deleted in the corresponding array, and so on. When an array is fetched and there are no elements, you can Add the remaining elements of the other array 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, the last sequence may have 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 merger

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;
  }
  //分解数组，递归排序
  $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);
}

Have you learned it? Everyone, please try it quickly.

Related recommendations:

PHP sorting algorithm series bucket sorting detailed explanation_php skills

PHP common sorting algorithm learning

Example analysis of basic commonly used sorting algorithms in JavaScript

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