Sorting algorithms — bubble, merge, quick sort — PHP usort() internals

Intermediate5 min read·eng-08-002

interviewcompare

Concept

Sorting algorithms — understanding the tradeoffs, not just the code. In practice, use PHP's built-in sort()/usort() (they use Timsort, an adaptive O(n log n) algorithm). Know sorting internals for interviews and for choosing the right approach.

Bubble Sort — O(n²) time, O(1) space. Compare adjacent pairs, swap if out of order. Repeat n times. Simple but slow — only useful as a teaching example.

Selection Sort — O(n²) time, O(1) space. Find the minimum, place it at position 0. Find the next minimum, place at position 1. Etc. Fewer swaps than bubble sort.

Insertion Sort — O(n²) worst, O(n) best (already sorted). Builds a sorted subarray by inserting each element in its correct position. Excellent for small arrays and nearly-sorted data. Used by Timsort for small chunks.

Merge Sort — O(n log n) guaranteed. Divide in half, sort each half recursively, merge. Stable (preserves order of equal elements). O(n) extra space for the merge step. Predictable performance.

Quick Sort — O(n log n) average, O(n²) worst (bad pivot). Pivot, partition into smaller/larger, recurse. In-place (no extra array). Fastest in practice for cache performance. PHP's sort uses Timsort (hybrid), not quicksort.

PHP's sort() family:

sort() / rsort(): Sort array values, re-index.
asort() / arsort(): Sort values, preserve keys.
ksort() / krsort(): Sort by keys.
usort(): Sort with a custom comparison function.
All use Timsort (hybrid merge + insertion sort). O(n log n).

Stability: A stable sort preserves the relative order of equal elements. Timsort (PHP) is stable. Quicksort is not stable.

Code Example

php

<?php
// Bubble sort — O(n²) — do NOT use in production
function bubbleSort(array $arr): array
{
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // already sorted optimization
    }
    return $arr;
}

// Merge sort — O(n log n), stable, O(n) space
function mergeSort(array $arr): array
{
    $n = count($arr);
    if ($n <= 1) return $arr;

    $mid   = intdiv($n, 2);
    $left  = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));

    return merge($left, $right);
}

function merge(array $left, array $right): array
{
    $result = [];
    $i = $j = 0;
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) $result[] = $left[$i++];
        else                          $result[] = $right[$j++];
    }
    return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}

// Quick sort — O(n log n) average, O(n²) worst
function quickSort(array $arr): array
{
    if (count($arr) <= 1) return $arr;

    $pivot    = $arr[0];
    $left     = array_filter(array_slice($arr, 1), fn($x) => $x <= $pivot);
    $right    = array_filter(array_slice($arr, 1), fn($x) => $x > $pivot);

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

// PHP built-in — use these in practice
$data = [5, 3, 8, 1, 9, 2];
sort($data);                                        // [1, 2, 3, 5, 8, 9]

$users = [['name' => 'Charlie', 'age' => 30], ['name' => 'Alice', 'age' => 25]];
usort($users, fn($a, $b) => $a['age'] <=> $b['age']); // sort by age ascending

// Multi-column sort (like SQL ORDER BY name ASC, age DESC)
usort($users, function ($a, $b) {
    return $a['name'] <=> $b['name'] ?: $b['age'] <=> $a['age'];
});

// usort internals: PHP's Timsort is O(n log n), stable, adaptive
// When array is already sorted or nearly sorted, Timsort approaches O(n)

PreviousBig-O notation — time and space complexity mental modelAlgorithms in PHP NextBinary search — O(log n) lookups on sorted dataAlgorithms in PHP