PHP/Sorting/MergeSort.php at master · TheAlgorithms/PHP · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<?php

declare(strict_types=1);

/**
 * Merge Sort
 *
 * @return array
 */
function mergeSort(array $arr)
{
    if (count($arr) <= 1) {
        return $arr;
    }

    $mid = intdiv(count($arr), 2);
    $leftArray = mergeSort(array_slice($arr, 0, $mid));
    $rightArray = mergeSort(array_slice($arr, $mid));

    return merge($leftArray, $rightArray);
}

function merge(array $leftArray, array $rightArray): array
{
    $result = [];
    $i = 0;
    $j = 0;

    while ($i < count($leftArray) && $j < count($rightArray)) {
        if ($rightArray[$j] > $leftArray[$i]) {
            $result[] = $leftArray[$i];
            $i++;
        } else {
            $result[] = $rightArray[$j];
            $j++;
        }
    }

    while ($i < count($leftArray)) {
        $result[] = $leftArray[$i];
        $i++;
    }

    while ($j < count($rightArray)) {
        $result[] = $rightArray[$j];
        $j++;
    }

    return $result;
}