PHP Merge Sort O(n log n)

merge-sort.php

<?php
function mergeSort(array $array) {
    $length = count( $array );

    // An array with one value is sorted
    if ( $length < 2 )
        return $array;

    // Split array in half
    $left = $right = [];
    $mid = floor($length / 2);

    for ( $i = 0; $i < $mid; $i++) {
        $left[] = $array[$i];
    }

    for ( $i = $mid; $i < $length; $i++ ) {
        $right[] = $array[$i];
    }

    // Sort left half, recursively
    $left = mergeSort($left);
    
    // Sort right half, recursively
    $right = mergeSort($right);

    // Now merge the two sorted halves together, in a sorted manner
    $left_length = count( $left );
    $right_length = count( $right );
    $l = $r = $k = 0;

    while ( $l < $left_length && $r < $right_length ) {
        if ( $left[$l] <= $right[$r] ) {
            $array[$k] = $left[$l];
            $l++;
        } else {
            $array[$k] = $right[$r];
            $r++;
        }
        $k++;
    }

    // A good chance we will be left over with one array still having more values
    while ( $l < $left_length ) {
        $array[$k] = $left[$l];
        $l++;
    }

    while ( $r < $right_length ) {
        $array[$k] = $right[$r];
        $r++;
    }

    return $array;
}