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];
        } else {
            $arr[$current] = $helper[$helperRight];


    // 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:

Understand Merge Sort:

Leave a Comment

Your email address will not be published. Required fields are marked *