Merge sort PHP implementation
After a short pause I am continuing my challenge to implement all sorting algorithms listed on Wikipedia in PHP. Merge sort is a bit more advanced than previous algorithms but once you figure it out it’s quite neat.
Personally, I hate recursion and try to avoid it as much as possible (speaking of recursion, check out my weblogs about Adjacency list model and Nested set model – which is in my opinion a better solution in most cases) – but sorting is one area where recursion is needed.
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).
Here is my PHP implementation 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;
-
}
Which will output a nice explanation of what’s happening, we can see what steps are being done and in what order:
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)
}
By the way, here are my previous posts from this challenge:
Hi very interesting the algorithm implementation, but could be better with the use of threads