# Merge Sort Algorithm in PHP

Merge sort guarantees O(n log n) runtime. It is usually compared with Quick Sort and is likely a second best sorting algorithm after Quick Sort in most cases. Quicksort is average case O(n log n), but has a worst case of O(n^2).  If you want to understand how Merge Sort works, jump to bottom of the page to see a quick video.

```function mergeSort(array \$arr) : array
{
\$helper = [];
\$low = 0;
\$high = count(\$arr)-1;
divideAndMerge(\$arr, \$helper, \$low, \$high);

return \$arr;
}

function divideAndMerge(array &\$arr, array &\$helper, int \$low, int \$high) : void
{
if (\$low < \$high) {
\$middle = (\$low + \$high) / 2;
divideAndMerge(\$arr, \$helper, \$low, \$middle);
divideAndMerge(\$arr, \$helper, \$middle+1, \$high);
merge(\$arr, \$helper, \$low, \$middle, \$high);
}
}

function merge(array &\$arr, array &\$helper, int \$low, int \$middle, int \$high) : void
{
//fill up helper array
foreach (\$arr as \$index => \$element) {
\$helper[\$index] = \$element;
}

\$helperLeft = \$low;
\$helperRight = \$middle+1;
\$current = \$low;

while (\$helperLeft <= \$middle && \$helperRight <= \$high) {
if (\$helper[\$helperLeft] <= \$helper[\$helperRight]) {
\$arr[\$current] = \$helper[\$helperLeft];
++\$helperLeft;
} else {
\$arr[\$current] = \$helper[\$helperRight];
++\$helperRight;
}

++\$current;
}

// copy the rest of the elements of left side into the array
// Right side doesn't need to copied because it is already there
// when we copied \$arr to \$helper

\$remaining = \$middle - \$helperLeft;
for (\$i = 0; \$i <= \$remaining; ++\$i) {
\$arr[\$current + \$i] = \$helper[\$helperLeft + \$i];
}

}```

Source Code of Algorithm Series: https://github.com/EresDev/Algorithms

Understand Merge Sort: 