Sorting Algorithms

Also Known As

TL;DR

Explanation

Key comparison-based sorts: Bubble (O(n²), educational only), Insertion (O(n²) worst, O(n) nearly-sorted — good for small arrays), Merge (O(n log n) stable, O(n) space), Quick (O(n log n) average, O(n²) worst), Heap (O(n log n), O(1) space). PHP's usort() uses Timsort — hybrid merge+insertion, O(n log n), stable. For integer keys, counting sort and radix sort achieve O(n). Stability matters when sorting objects by multiple fields.

Diagram

flowchart TD
    subgraph Comparison Sorts
        QUICK[Quicksort<br/>O n log n avg<br/>O n^2 worst]
        MERGE[Mergesort<br/>O n log n stable<br/>O n space]
        HEAP[Heapsort<br/>O n log n<br/>O 1 space]
    end
    subgraph Non-comparison
        COUNT[Counting Sort<br/>O n+k integers only]
        RADIX[Radix Sort<br/>O nk fixed-length keys]
    end
    PHP[PHP usort<br/>Timsort = Merge+Insertion<br/>O n log n stable]
    style PHP fill:#238636,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Sorting inside a loop when sorting once before would suffice.
• Using usort() with a comparator that returns bool instead of negative/zero/positive — causes incorrect ordering.
• Not using a stable sort when secondary sort order matters — usort() in PHP 8 is stable but older versions were not.
• Reinventing a sort instead of using PHP's built-in usort()/uasort() which use Timsort.

Code Examples

// Sort inside loop — O(n² log n):
foreach ($categories as $category) {
    usort($items, fn($a, $b) => $a->price <=> $b->price); // Re-sorts every iteration
    displayCategory($category, $items);
}

// Sort once before the loop — O(n log n) total:
usort($items, fn($a, $b) => $a->price <=> $b->price);
foreach ($categories as $category) {
    displayCategory($category, $items); // Uses pre-sorted array
}

References

• ↗ https://en.wikipedia.org/wiki/Sorting_algorithm

Tags

Related Terms