benchmark of PHP stable sort

bench.log

                 overhead(shuffled  ):  0.0017560 2420,3297,5637,1083,5790
                 overhead(duplicated):  0.0017490 622,4325,1760,1691,4110
                 overhead(sorted    ):  0.0005720 1,2,3,4,5
                mergesort(shuffled  ):  0.9389420 1,10,100,1000,10000
                mergesort(duplicated):  0.9406991 1,1,10,10,100
                mergesort(sorted    ):  0.3923521 1,10,100,1000,10000
    schwartzian_transform(shuffled  ):  0.6981239 1,10,100,1000,10000
    schwartzian_transform(duplicated):  0.6524200 1,1,10,10,100
    schwartzian_transform(sorted    ):  0.6394210 1,10,100,1000,10000
   schwartzian_transform2(shuffled  ):  0.6490870 1,10,100,1000,10000
   schwartzian_transform2(duplicated):  0.6422801 1,1,10,10,100
   schwartzian_transform2(sorted    ):  0.6515610 1,10,100,1000,10000
   schwartzian_transform3(shuffled  ):  0.6619020 1,10,100,1000,10000
   schwartzian_transform3(duplicated):  0.6538131 1,1,10,10,100
   schwartzian_transform3(sorted    ):  0.6571951 1,10,100,1000,10000

bench.php

<?php
// PHP で stable sort する各方法のベンチマーク

// オーバーヘッドの計測用
function overhead(&$array, $cmp_function = 'strcmp') {
    return;
}

// http://jp.php.net/manual/ja/function.usort.php のコメントに載っているマージソート
// →PHP 側の処理が多いため比較的遅いが、ソート済みの場合はマージ処理が走らないため速い
function mergesort(&$array, $cmp_function = '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, $cmp_function);
    mergesort($array2, $cmp_function);
    // If all of $array1 is <= all of $array2, just append them.
    if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) {
        $array = array_merge($array1, $array2);
        return;
    }
    // Merge the two sorted arrays into a single sorted array
    $array = array();
    $ptr1 = $ptr2 = 0;
    while ($ptr1 < count($array1) && $ptr2 < count($array2)) {
        if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) {
            $array[] = $array1[$ptr1++];
        }
        else {
            $array[] = $array2[$ptr2++];
        }
    }
    // Merge the remainder
    while ($ptr1 < count($array1)) $array[] = $array1[$ptr1++];
    while ($ptr2 < count($array2)) $array[] = $array2[$ptr2++];
    return;
}

// Perl でよく行われるシュワルツ変換（ http://en.wikipedia.org/wiki/Schwartzian_transform ）風の処理
// 上の例に合わせて破壊的な処理にしているが、非破壊的な関数にすることも可能。
// →対象がシャッフルされた状態ではこちらのほうが速いが、ソートが必要ない場合も同じ程度の時間がかかる
function schwartzian_transform(&$array, $cmp_function = 'strcmp') {
    $indexedArray = array();
    foreach ($array as $i => $e) {
        $indexedArray[] = array($e, $i);
    }
    usort(
        $indexedArray,
        function($a, $b) use ($cmp_function) {
            return $cmp_function($a[0], $b[0]) ?: $a[1] - $b[1];
        }
    );
    $array = array_map(
        function($e) {
            return $e[0];
        },
        $indexedArray
    );
    return;
}

// シュワルツ変換風のでループを排除して array_map に変えてみた
// →上記と大差なし（微妙に遅い？）
function schwartzian_transform2(&$array, $cmp_function = 'strcmp') {
    $i = 0;
    $indexedArray = array_map(
        function($e) use ($i) {
            return array($e, $i++);
        },
        $array
    );
    usort(
        $indexedArray,
        function($a, $b) use ($cmp_function) {
            return $cmp_function($a[0], $b[0]) ?: $a[1] - $b[1];
        }
    );
    $array = array_map(
        function($e) {
            return $e[0];
        },
        $indexedArray
    );
    return;
}

// さらに処理を簡易に
// →上記と大差なし（微妙に遅い？）
function schwartzian_transform3(&$array, $cmp_function = 'strcmp') {
    $i = 0;
    $indexedArray = array_map(
        function($e) use ($i) {
            return array($e, $i++);
        },
        $array
    );
    usort(
        $indexedArray,
        function($a, $b) use ($cmp_function) {
            return $cmp_function($a[0], $b[0]) ?: $a[1] - $b[1];
        }
    );
    $array = array_map('current', $indexedArray);
    return;
}

// 以降はベンチマークの取得処理

$funcs = array(
    'overhead',
    'mergesort',
    'schwartzian_transform',
    'schwartzian_transform2',
    'schwartzian_transform3',
);

// 以下の 3 種類のデータで検証する

// (1) 完全にシャッフルされた配列
$array_shuffled = range(1, 10000);
shuffle($array_shuffled);

// (2) 重複要素を持つ配列
$array_duplicated = array_merge(range(1, 5000), range(1, 5000));
shuffle($array_duplicated);

// (3) ソート済みの配列
$array_sorted = range(1, 10000);

$tries = array(
    'shuffled'   => $array_shuffled,
    'duplicated' => $array_duplicated,
    'sorted'     => $array_sorted,
);
foreach ($funcs as $func) {
    foreach ($tries as $try => $ary) {
        $array = $ary;
        $time_start = microtime(true);
        $func($array);
        $time_end = microtime(true); $time = $time_end - $time_start;
        printf("%25s(%-10s): %10.7f %s\n", $func, $try, $time, implode(',', array_slice($array, 0, 5)));
    }
}
echo "\n";