JIYIK CN >

I have previously written about the introduction to merge sort, The Path to Learning Sorting Algorithms - Merge Sort . It has been a long time since then. Now I will reorganize it and talk about merge sort in detail from the code level.

Merge sort algorithm

As usual, for sorting algorithms, let's first list the concepts

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.

merge

From the concept, we can also see that since it is merge sort, the core problem is how to merge. This can be attributed to a merging problem from small to large.

Given a set of data

We use the divide-and-conquer strategy to split it until it can no longer be split. The desired effect is as follows

This is the split array that we will eventually use for merging. Let's start merging

We can see that every two arrays are merged. The new array after merging is in order. Then the new arrays are merged two by two until they are merged into a final array.

Below we take the last step of merging as an example to introduce the detailed steps of merging two arrays.

In the first step, the elements at positions sl and sr are compared, the element with the smaller value is put into the new array, and then the corresponding index sl/sr is moved forward one position. Here, the 2 at position sl is smaller, so 2 is put into the new array, and sl is moved to the next element of the group.

Step 2: Compare the elements at the positions of sl and sr again. 3 is smaller than 6, so 3 is put into the new array and sl is moved to the next element again.

Step 3: Continue to compare the two. At this time, 6 on sr is smaller than 7 on sl. Therefore, 6 is put into the new array and sr moves to the next element of the group.

Step 4: Repeat the above comparison process until one group is put into the new array before the other group.

Finally, the sl group has been sorted, and the remaining elements of the sr group can be directly put into the new array, because the elements in each group are in order.

At this point we can see that the entire merge process has been completed. Let's take a look at the code for the merge process.

function Merge($arr,$l,$m,$r)
{
    $t = $arr;
    $lstart = $l;
    $rstart = $m+1;

    while($l < $r) {
        if($lstart > $m || $rstart > $r) break;
        if($arr[$lstart] > $arr[$rstart]) {
            $t[$l++] = $arr[$rstart++];
        }else{
            $t[$l++] = $arr[$lstart++];
        }
    }

    $start = $l;
    $end = $r;

    if($lstart <= $m) {
        $start = $lstart;
        $end = $m;
    }elseif($rstart <= $r) {
        $start = $rstart;
        $end = $r;
    }

    while($start <= $end) {
        $t[$l++] = $arr[$start++];
    }
    $arr = $t;

    return $arr;
}

Split

Above we have seen the core process of merge sort, merging. However, the merging process alone is still incomplete, because the original data given to us is a complete set of data. Therefore, we should split it before merging.

The splitting process is relatively simple. It does not involve sorting issues. It's just splitting.

The code for the splitting process here can be divided into two ways: recursive implementation and non-recursive implementation

Let's take a look at two different split codes.

recursion

The recursive code is very simple. We only need to set the recursive termination condition and then write the code according to the overall outline.

function MergeSort(&$arr,$l,$r)
{
    if($l >= $r) {
        return;
    }
    $m = floor(($l+$r) / 2);

    MergeSort($arr,$l,$m);
    MergeSort($arr,$m+1,$r);
    $arr = Merge($arr,$l,$m,$r);
}

We can see that the code is very simple. In a depth-first manner, we split the left side first, then the right side. Finally, we call the Merge() function above to merge them.

Non-recursive

The non-recursive code is a bit complicated. In the above recursive splitting process, we only set the conditions for terminating the recursion, and other details do not need to be considered. However, the non-recursive method must consider the details.

Because the splitting process is a depth-first process, a stack mechanism is needed here for depth-first.

In fact, the underlying implementation mechanism of recursion is also implemented with the help of the stack mechanism.

Here we look at the code

function MergeSort(&$arr)
{
    $stack = []; //  初始化一个栈
    $toMergeStack = []; // 用于归并的栈
    $l = 0;
    $r = count($arr) - 1;

    $tmp = [$l,$r,floor(($l+$r)/2)];

    array_push($stack,$tmp);
    array_push($toMergeStack,$tmp);

    while(!empty($stack)) {
        $s = array_pop($stack);
        if($s[0] < $s[2]) {
            array_push($stack,[$s[0],$s[2],floor(($s[0]+$s[2])/2)]);
            array_push($toMergeStack,[$s[0],$s[2],floor(($s[0]+$s[2])/2)]);
        }

        if($s[2]+1 < $s[1]) {
            array_push($stack,[$s[2]+1,$s[1],floor(($s[2]+1+$s[1])/2)]);
            array_push($toMergeStack,[$s[2]+1,$s[1],floor(($s[2]+1+$s[1])/2)]);
        }
    }

    // 开始合并
    while(!empty($toMergeStack)){
        $s = array_pop($toMergeStack);
        $arr = Merge($arr,$s[0],$s[2],$s[1]);
    }
}

If we look at the code again, it is obvious that there is a lot more code. But the process is not complicated. Understanding the non-recursive method will help us understand merge sort better.