PHP Mergesort

php

This is an example of a method that sorts an array in a stable way.

Stable means that if the compare function regards two items as having the same 'weight' (compare function returns 0), the original order will not be changed.

This method is changed somewhat from the below source to preserve keys of the array.

Source: stackoverflow

Usage:

<?php
$array = array(
    'A' => array('sort' => 3),
    'B' => array('sort'=> 2),
    'C' => array('sort'=> 2),
    'D' => array('sort' => 1),
);

mergeSort($array, function($item1, $item2) {
    if($item1['sort'] == $item1['sort']) {
        return 0;
    }
    return ($item1['sort'] < $item1['sort'])?-1:1;
});

Code:

<?php
/**
 * Since uasort don't preserve the order of an array if the comparison is equal
 * we have to resort to a merge sort. It's quick and stable: O(n*log(n)).
 * 
 * @param array &$array - the array to sort
 * @param callable $cmpFunction - the function to use for comparison
 */ 
function mergeSort(&$array, $cmpFunction = 'strcmp') {
    // Arrays of size < 2 require no action.
    if (count($array) < 2) {
        return;
    }
    // Split the array in half
    $halfway = count($array) / 2;
    $array1 = array_slice($array, 0, $halfway);
    $array2 = array_slice($array, $halfway);
    // Recurse to sort the two halves
    mergeSort($array1, $cmpFunction);
    mergeSort($array2, $cmpFunction);
    // If all of $array1 is <= all of $array2, just append them.
    if(call_user_func($cmpFunction, end($array1), reset($array2)) < 1) {
        $array = array_merge($array1, $array2);
        return;
    }
    // Merge the two sorted arrays into a single sorted array
    $array = array();
    $val1 = reset($array1);
    $val2 = reset($array2);
    do {
        if (call_user_func($cmpFunction, $val1, $val2) < 1) {
            $array[key($array1)] = $val1;
            $val1 = next($array1);
        } else {
            $array[key($array2)] = $val2;
            $val2 = next($array2);
        }
    } while($val1 && $val2);

    // Merge the remainder
    while($val1) {
        $array[key($array1)] = $val1;
        $val1 = next($array1);
    }
    while($val2) {
        $array[key($array2)] = $val2;
        $val2 = next($array2);
    }
    return;
}