PHP array quick sort vs. merge sort

Quick sort is a recursive algorithm that divides the array into smaller elements and larger elements and sorts them recursively, while merge sort recursively divides the array into smaller arrays, sorts each small array, and then merges it. Return the original array. The codes implemented by PHP are: Quick sort: Divide the array into elements smaller than and larger than the baseline value, and then sort each part recursively. Merge sort: Recursively divide an array into smaller arrays, sort each smaller array, and then merge the sorted smaller arrays back into the original array.

PHP array quick sort vs. merge sort

#What are quick sort and merge sort?

Quick sort and merge sort are both common algorithms used to sort arrays.

• Quick sort: Divide the array into two parts, one containing smaller elements and the other containing larger elements, and then sort each part recursively.
• Merge sort: Recursively divide the array into smaller arrays, sort each smaller array, and then merge the sorted smaller arrays back into the original array.

Code implementation

The following are quick sort and merge sort functions implemented in PHP:

Quick sort:

function quickSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $pivot = $arr[0];
    $left = [];
    $right = [];
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

Merge sort:

function mergeSort($arr) {
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $mid = floor($length / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];
    $lIndex = $rIndex = 0;
    while ($lIndex < count($left) && $rIndex < count($right)) {
        if ($left[$lIndex] < $right[$rIndex]) {
            $result[] = $left[$lIndex++];
        } else {
            $result[] = $right[$rIndex++];
        }
    }
    while ($lIndex < count($left)) {
        $result[] = $left[$lIndex++];
    }
    while ($rIndex < count($right)) {
        $result[] = $right[$rIndex++];
    }
    return $result;
}

Practical case

Consider an unordered integer array[5 , 2, 8, 3, 1, 9, 4, 7, 6].

Use quick sort:

$sortedArray = quickSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Use merge sort :

$sortedArray = mergeSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

The above is the detailed content of PHP array quick sort vs. merge sort. For more information, please follow other related articles on the PHP Chinese website!