PHP Merge Sort

Wiki

Merge sort was invented by John Von Neumann, a big name in computer science history. It is a divide and conquer algorithm. It sorts arrays by dividing them recursively into halves (divide) and then sorting and merging them back together (conquer).

The good thing about this algorithm is it preserves order of equal elements (if you have two 25s in an array, merge sort will place the one that came earlier in the original array on the left side).

Example (consisting of two functions: divide and conquer)

<?php
 
$arr = array();
for ($i = 0; $i < 100; ++$i) {
    $arr[] = $i;
}
shuffle($arr);
$sortedArr = divide($arr);
var_dump($sortedArr);
 
function divide(array $arr) {
    if (1 === count($arr)) {
        return $arr;
    }
    $left = $right = array();
    $middle = round(count($arr)/2);
    for ($i = 0; $i < $middle; ++$i) {
        $left[] = $arr[$i];
    }
    for ($i = $middle; $i < count($arr); ++$i) {
        $right[] = $arr[$i];
    }
    $left = divide($left);
    $right = divide($right);
    return conquer($left, $right);
}
 
function conquer(array $left, array $right) {
    $result = array();
    while (count($left) > 0 || count($right) > 0) {
        if (count($left) > 0 && count($right) > 0) {
            $firstLeft = current($left);
            $firstRight = current($right);
            if ($firstLeft <= $firstRight) {
                $result[] = array_shift($left);
            } else {
                $result[] = array_shift($right);
            }
        } else if (count($left) > 0) {
            $result[] = array_shift($left);
        } else if (count($right) > 0) {
            $result[] = array_shift($right);
        }
    }
    return $result;
}

Which will output

array(100) {
  [0]=>
  int(0)
  [1]=>
  int(1)
  [2]=>
  int(2)
  [3]=>
  int(3)
  [4]=>
  int(4)
  [5]=>
  int(5)
  [6]=>
  int(6)
  [7]=>
  int(7)
  [8]=>
  int(8)
  [9]=>
  int(9)
  [10]=>
  int(10)
  [11]=>
  int(11)
  [12]=>
  int(12)
  [13]=>
  int(13)
  [14]=>
  int(14)
  [15]=>
  int(15)
  [16]=>
  int(16)
  [17]=>
  int(17)
  [18]=>
  int(18)
  [19]=>
  int(19)
  [20]=>
  int(20)
  [21]=>
  int(21)
  [22]=>
  int(22)
  [23]=>
  int(23)
  [24]=>
  int(24)
  [25]=>
  int(25)
  [26]=>
  int(26)
  [27]=>
  int(27)
  [28]=>
  int(28)
  [29]=>
  int(29)
  [30]=>
  int(30)
  [31]=>
  int(31)
  [32]=>
  int(32)
  [33]=>
  int(33)
  [34]=>
  int(34)
  [35]=>
  int(35)
  [36]=>
  int(36)
  [37]=>
  int(37)
  [38]=>
  int(38)
  [39]=>
  int(39)
  [40]=>
  int(40)
  [41]=>
  int(41)
  [42]=>
  int(42)
  [43]=>
  int(43)
  [44]=>
  int(44)
  [45]=>
  int(45)
  [46]=>
  int(46)
  [47]=>
  int(47)
  [48]=>
  int(48)
  [49]=>
  int(49)
  [50]=>
  int(50)
  [51]=>
  int(51)
  [52]=>
  int(52)
  [53]=>
  int(53)
  [54]=>
  int(54)
  [55]=>
  int(55)
  [56]=>
  int(56)
  [57]=>
  int(57)
  [58]=>
  int(58)
  [59]=>
  int(59)
  [60]=>
  int(60)
  [61]=>
  int(61)
  [62]=>
  int(62)
  [63]=>
  int(63)
  [64]=>
  int(64)
  [65]=>
  int(65)
  [66]=>
  int(66)
  [67]=>
  int(67)
  [68]=>
  int(68)
  [69]=>
  int(69)
  [70]=>
  int(70)
  [71]=>
  int(71)
  [72]=>
  int(72)
  [73]=>
  int(73)
  [74]=>
  int(74)
  [75]=>
  int(75)
  [76]=>
  int(76)
  [77]=>
  int(77)
  [78]=>
  int(78)
  [79]=>
  int(79)
  [80]=>
  int(80)
  [81]=>
  int(81)
  [82]=>
  int(82)
  [83]=>
  int(83)
  [84]=>
  int(84)
  [85]=>
  int(85)
  [86]=>
  int(86)
  [87]=>
  int(87)
  [88]=>
  int(88)
  [89]=>
  int(89)
  [90]=>
  int(90)
  [91]=>
  int(91)
  [92]=>
  int(92)
  [93]=>
  int(93)
  [94]=>
  int(94)
  [95]=>
  int(95)
  [96]=>
  int(96)
  [97]=>
  int(97)
  [98]=>
  int(98)
  [99]=>
  int(99)
}

Best way to understand how it works is to apply it to a smaller array and add a little debugging inside the functions so we can see what’s happening. After a little tweaking:

<?php
 
$arr = array(4, 5, 1, 3, 2);
$sortedArr = divide($arr);
var_dump($sortedArr);
 
function divide(array $arr) {
    if (1 === count($arr)) {
        return $arr;
    }
    $left = $right = array();
    $middle = round(count($arr)/2);
    for ($i = 0; $i < $middle; ++$i) {
        $left[] = $arr[$i];
    }
    for ($i = $middle; $i < count($arr); ++$i) {
        $right[] = $arr[$i];
    }
    $left = divide($left);
    $right = divide($right);
    echo "We are going to conquer these two arrays:\narray(",
    implode(", ", $left), ")\narray(", implode(", ", $right), ")\n";
    $conquered = conquer($left, $right);
    echo "After conquering we get: array(", implode(", ", $conquered), ")\n\n";
    return $conquered;
}
 
function conquer(array $left, array $right) {
    $result = array();
    while (count($left) > 0 || count($right) > 0) {
        if (count($left) > 0 && count($right) > 0) {
            $firstLeft = current($left);
            $firstRight = current($right);
            if ($firstLeft <= $firstRight) {
                $result[] = array_shift($left);
            } else {
                $result[] = array_shift($right);
            }
        } else if (count($left) > 0) {
            $result[] = array_shift($left);
        } else if (count($right) > 0) {
            $result[] = array_shift($right);
        }
    }
    return $result;
}
We are going to conquer these two arrays:
array(4)
array(5)
After conquering we get: array(4, 5)

We are going to conquer these two arrays:
array(4, 5)
array(1)
After conquering we get: array(1, 4, 5)

We are going to conquer these two arrays:
array(3)
array(2)
After conquering we get: array(2, 3)

We are going to conquer these two arrays:
array(1, 4, 5)
array(2, 3)
After conquering we get: array(1, 2, 3, 4, 5)

array(5) {
  [0]=>
  int(1)
  [1]=>
  int(2)
  [2]=>
  int(3)
  [3]=>
  int(4)
  [4]=>
  int(5)
}
0.00 avg. rating (0% score) - 0 votes