JIYIK CN >

Let's first look at the definition of merge sort

Merge sort is an effective sorting algorithm based on the merge operation. This algorithm is a very typical application of the Divide and Conquer method. Merge the ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence ordered, and then make the subsequence segments ordered. If two ordered lists are merged into one ordered list, it is called a two-way merge.

Simply put, it merges two ordered lists into one ordered list.

Let's first understand the process of merge sort through the following figure.

Let's look at the steps of how to decompose and then merge

1. Apply for space whose size is the sum of the two sorted sequences. This space is used to store the merged sequence.
2. Set two pointers, the initial positions of which are the starting positions of the two sorted sequences.
3. Compare the elements pointed to by the two pointers, select the relatively small element and put it into the merge space, and move the pointer to the next position
4. Repeat step 3 until a pointer reaches the end of the sequence
5. Copy all remaining elements of the other sequence directly to the end of the merged sequence

Finally, we implemented the merge sort algorithm using PHP

function Merge($arr,$l,$m,$r){
    $t = $arr;
    $start = $l;
    $end = $m+1;
    while($l<=$r){
        if($l>$m||$end>$r) break;
        if($arr[$l]<$arr[$end]){
            $t[$start++] = $arr[$l++];
        }else{
            $t[$start++] = $arr[$end++];
        }
    }
    if($l<=$m){
        $s = $l;
        $e = $m;
    }elseif($r>=$end){
        $s = $end;
        $e = $r;
    }
    while($s<=$e){
        $t[$start++] = $arr[$s++];
    }
    $arr = $t;
    return $arr;
}
function MergeSort(&$arr,$l,$r){
   if($r <= $l) return ;
   $m = floor(($l+$r)/2);
   MergeSort($arr,$l,$m);
   MergeSort($arr,$m+1,$r);
   $arr = Merge($arr,$l,$m,$r);
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
MergeSort($arr,0,count($arr)-1);
print_r($arr);

The above code is implemented using a recursive mechanism. Of course, it can also be implemented in a non-recursive form. You can refer to the article "Merge Sort (Non-recursive Implementation)" .

Using PHP to implement merge sort, according to the above code, the code is relatively cumbersome. PHP has its own characteristics, and can use less code to implement merge sort. However, the above code can better reflect the entire decomposition and merging process. So if you are learning the merge sort algorithm, it is recommended to use the above code. Although the code is cumbersome, it is very helpful for understanding the merge sort process.

For a more detailed merge sort algorithm, I have written a new article to fully understand the merge sort algorithm , which you can refer to.