Quicksort – variants, Introsort, benchmark vs native sort()

Quicksort is the most widely used sorting algorithm in practice – it is the basis of PHP’s built-in sort(), most standard library implementations, and many database engines. I show the classic recursive implementation, the three-way partition variant for arrays with many duplicates, and benchmark it against PHP’s native sort() and usort() to see when writing your own makes any sense at all.

Classic Quicksort – recursive

<?php

declare(strict_types=1);

function quicksort(array $arr): array
{
    $n = count($arr);
    if ($n <= 1) return $arr;

    $pivot = $arr[array_key_first($arr)]; // first element as pivot
    $left  = [];
    $right = [];

    foreach (array_slice($arr, 1) as $item) {
        if ($item <= $pivot) {
            $left[] = $item;
        } else {
            $right[] = $item;
        }
    }

    return array_merge(quicksort($left), [$pivot], quicksort($right));
}

print_r(quicksort([8, 3, 5, 1, 9, 2, 7, 4, 6]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

In-place Quicksort - with Lomuto partition

<?php

declare(strict_types=1);

// In-place version avoids creating sub-arrays - O(log n) space instead of O(n)
function quicksortInPlace(array &$arr, int $low, int $high): void
{
    if ($low >= $high) return;

    // Partition returns the final position of the pivot
    $pivotIndex = partition($arr, $low, $high);

    quicksortInPlace($arr, $low, $pivotIndex - 1);
    quicksortInPlace($arr, $pivotIndex + 1, $high);
}

function partition(array &$arr, int $low, int $high): int
{
    $pivot = $arr[$high]; // last element as pivot
    $i     = $low - 1;   // index of smaller element

    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] <= $pivot) {
            $i++;
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]]; // swap
        }
    }

    [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]]; // place pivot
    return $i + 1;
}

$data = [8, 3, 5, 1, 9, 2, 7, 4, 6];
quicksortInPlace($data, 0, count($data) - 1);
print_r($data); // sorted in place

Three-way partition - for arrays with duplicates

<?php

// Djikstra's three-way partition handles duplicates efficiently
// Splits into: less than pivot | equal to pivot | greater than pivot
// The "equal" partition is done in one pass - no further recursion needed

function threeWayQuicksort(array &$arr, int $low, int $high): void
{
    if ($low >= $high) return;

    $lt  = $low;
    $gt  = $high;
    $i   = $low + 1;
    $pivot = $arr[$low];

    while ($i <= $gt) {
        if ($arr[$i] < $pivot) {
            [$arr[$lt], $arr[$i]] = [$arr[$i], $arr[$lt]];
            $lt++; $i++;
        } elseif ($arr[$i] > $pivot) {
            [$arr[$i], $arr[$gt]] = [$arr[$gt], $arr[$i]];
            $gt--;
        } else {
            $i++;
        }
    }

    threeWayQuicksort($arr, $low, $lt - 1);
    threeWayQuicksort($arr, $gt + 1, $high);
}

// With many duplicates - three-way is dramatically faster
$data = array_merge(array_fill(0, 300, 5), range(1, 100), array_fill(0, 300, 5));
threeWayQuicksort($data, 0, count($data) - 1);

Introsort - what PHP actually uses

PHP's internal sort() is not pure Quicksort. It uses Introsort: Quicksort up to a depth limit, then switches to Heapsort to guarantee O(n log n) worst case. This prevents Quicksort's O(n²) worst case on sorted or near-sorted arrays.

<?php

// Quicksort worst case: already sorted array
// With first element as pivot: O(n²) - pivot never divides the array
$sorted = range(1, 1000);
// Pure quicksort with first pivot = very slow on $sorted!
// PHP's sort() = Introsort = still fast because it detects and switches to Heapsort

// Median-of-three pivot selection prevents the worst case
function medianOfThree(array &$arr, int $low, int $mid, int $high): int
{
    if ($arr[$low] > $arr[$mid])   [$arr[$low], $arr[$mid]]  = [$arr[$mid], $arr[$low]];
    if ($arr[$low] > $arr[$high])  [$arr[$low], $arr[$high]] = [$arr[$high], $arr[$low]];
    if ($arr[$mid] > $arr[$high])  [$arr[$mid], $arr[$high]] = [$arr[$high], $arr[$mid]];
    return $mid; // median is now at $mid
}

Benchmark - PHP sort() vs custom Quicksort

<?php

$size = 100_000;
$data = array_map(fn() => random_int(1, 1_000_000), range(1, $size));

// PHP native sort() - Introsort in C
$arr   = $data;
$start = microtime(true);
sort($arr);
$nativeTime = (microtime(true) - $start) * 1000;

// PHP quicksort (recursive with new arrays) - PHP code
$start = microtime(true);
quicksort($data);
$phpTime = (microtime(true) - $start) * 1000;

echo "Native sort(): {$nativeTime}ms\n";  // ~5ms
echo "PHP quicksort: {$phpTime}ms\n";     // ~350ms

// PHP code is ~70x slower than the C implementation
// Never use custom sort implementations in production - use sort(), usort(), uasort()

Summary

Quicksort is worth understanding thoroughly - it teaches partitioning, pivot selection, and worst-case analysis in one elegant algorithm. In practice, never use a custom PHP sort implementation over native functions which run in C at ~70x the speed. The exception is when you need a very specific comparison logic that usort() cannot express cleanly - but that is rare. Know Quicksort. Use sort().