JIYIK CN >

In the article "Merge Sort", we introduced the principles and operation steps of merge sort, and finally implemented the sorting algorithm using PHP code. In the program, we used the principle of recursion to implement the algorithm.

In fact, the underlying mechanism of recursive function is nothing more than the stack mechanism. In this article, we will not use recursive function, but directly use the stack mechanism to implement merge sort.

First, let's briefly introduce the basic principles of non-recursive implementation:

First we need to apply for two stacks - stack, stack1;

The first step is to push the starting position s, the end position e and the middle position m of the sequence to be sorted into stack1.

Step 2: Pop the data from stack1 and push the popped data into stack. Then determine whether s is less than m. If s is less than m, put s as the starting position, m as the end position, and (s+m)/2 as the middle position into stack1. Then determine whether m+1 is less than e. If m+1 is less than e, put m+1 as the starting position, e as the end position, and (m+1+e)/2 as the middle position into stack1.

Step 3: Check whether stack1 is empty. If it is empty, proceed to step 4. If it is not empty, repeat step 2.

Step 4: Pop the data from the stack and merge them according to the starting position, end position and middle position of the popped data (the merging process is the same as in the previous article).

Step 5: Check whether the stack is empty. If it is not empty, repeat step 4. If it is empty, the program ends.

Let's look at the implementation code

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){
    $stack = array();
    $stack1 = array();
    $temp = array(0,count($arr)-1,floor((0+count($arr)-1)/2));
    array_push($stack1,$temp);
    while(count($stack1)>0){
        $temp = array_pop($stack);
        array_push($stack,$temp);
        if($temp[0]<$temp[2]){
            array_push($stack1,array($temp[0],$temp[2],floor(($temp[0]+$temp[2])/2)));
        }
        if($temp[2]+1<$temp[1]){
            array_push($stack1,array($temp[2]+1,$temp[1],floor(($temp[2]+1+$temp[1])/2)));
        }
    }
    while(count($stack)>0){
        $temp = array_pop($stack);
        $arr = Merge($arr,$temp[0], $temp[2], $temp[1]);
    }
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
MergeSort($arr);
print_r($arr);

Compared with the recursive method, this method has more code. However, considering the principle of merge sort, I personally think this method is easier to understand than the recursive method. After all, the implementation of recursion also relies on the stack mechanism. By directly operating the stack to implement the merge algorithm, we will have a deeper understanding of merge sort.

I have written another article about merge sort to give you a comprehensive understanding of the merge sort algorithm . It explains the splitting and merging process of merge sort in more detail, and the code includes both recursive and non-recursive implementations.

I hope this helps.