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:

Leave a Reply

avatar
  Subscribe  
Notify of