⚙️ Sorting Algorithms — Complete Guide

Index: Sorting Index | Parent: Array Index

How to Think About Sorting in Interviews

Step 1 — Ask yourself these questions:

Is the data already nearly sorted? → Insertion Sort
Is it integers with a small range (0–100)? → Counting Sort
Is it large integers / IDs / phone numbers? → Radix Sort
Is it floats uniformly distributed [0,1)? → Bucket Sort
Do I need stable sort (preserve equal-element order)? → Merge Sort
Is memory limited? → Heap Sort
General purpose, fastest in practice? → Quick Sort
PHP/Laravel/JS built-in sort? → Tim Sort (used internally)

Bubble Sort

Concept: Compare adjacent pairs. Swap if wrong order. Repeat. Largest "bubbles" to end each pass.

Pass 1: [5,3,1,4,2] → [3,1,4,2,5]  (5 bubbles to end)
Pass 2: [3,1,4,2,5] → [1,3,2,4,5]
Pass 3: [1,3,2,4,5] → [1,2,3,4,5]

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 — O(n) best case
    }
    return $arr;
}

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let 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;
    }
    return arr;
}

Best	Average	Worst	Space	Stable
O(n)	O(n²)	O(n²)	O(1)	✅

Use in interview: Explain the optimization (swapped flag). Shows you know O(n) best case.

Selection Sort

Concept: Find minimum in unsorted portion. Swap it to front. Advance boundary.

[5,3,1,4,2]
 ^min=1      → swap 5 and 1 → [1,3,5,4,2]
   ^min=2    → swap 3 and 2 → [1,2,5,4,3]
     ^min=3  → swap 5 and 3 → [1,2,3,4,5]

function selectionSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIdx = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIdx]) {
                $minIdx = $j;
            }
        }
        if ($minIdx !== $i) {
            [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
        }
    }
    return $arr;
}

Best	Average	Worst	Space	Stable
O(n²)	O(n²)	O(n²)	O(1)	❌

When to use: When number of swaps must be minimized (write-expensive storage).

Insertion Sort

Concept: Like sorting playing cards. Take one card at a time, insert it into the correct position in the already-sorted left part.

[5,3,1,4,2]
 [5] → insert 3 → [3,5]
       insert 1 → [1,3,5]
             insert 4 → [1,3,4,5]
                   insert 2 → [1,2,3,4,5]

function insertionSort(array $arr): array {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        // Shift elements greater than key one position right
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

Best	Average	Worst	Space	Stable
O(n)	O(n²)	O(n²)	O(1)	✅

When to use:

Nearly sorted data (O(n) performance!)
Small arrays (< 20 elements)
Used inside TimSort for small sub-arrays

Merge Sort

Concept: Divide array in half recursively until size 1. Then merge sorted halves back together.

[5,3,1,4,2]
 [5,3,1] [4,2]
  [5,3] [1]  [4] [2]
  [3,5]  [1] [2,4]
    [1,3,5]  [2,4]
      [1,2,3,4,5]

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++];
        }
    }

    while ($i < count($left))  $result[] = $left[$i++];
    while ($j < count($right)) $result[] = $right[$j++];

    return $result;
}

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left  = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) result.push(left[i++]);
        else result.push(right[j++]);
    }
    return [...result, ...left.slice(i), ...right.slice(j)];
}

Best	Average	Worst	Space	Stable
O(n log n)	O(n log n)	O(n log n)	O(n)	✅

When to use: Guaranteed O(n log n), stable, good for linked lists, external sorting.

Quick Sort

Concept: Pick a pivot. Put smaller elements left, larger right. Recursively sort both halves.

[5,3,1,4,2]  pivot=2
Left of 2: [1]   Right of 2: [5,3,4]
               pivot=4: Left=[3] Right=[5]
Result: [1,2,3,4,5]

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

    // Lomuto partition — pick last element as pivot
    $pivot = $arr[$n - 1];
    $left  = [];
    $right = [];

    for ($i = 0; $i < $n - 1; $i++) {
        if ($arr[$i] <= $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

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

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivot = arr[arr.length - 1];
    const left  = arr.slice(0, -1).filter(x => x <= pivot);
    const right = arr.slice(0, -1).filter(x => x > pivot);
    return [...quickSort(left), pivot, ...quickSort(right)];
}

Best	Average	Worst	Space	Stable
O(n log n)	O(n log n)	O(n²)	O(log n)	❌

Worst case trigger: Already sorted array with bad pivot choice (always pick last). Fix: Random pivot or median-of-three pivot.

When to use: General purpose, fastest in practice, used in most standard libraries.

Heap Sort

Concept: Build a max-heap. Repeatedly extract the maximum (root), placing it at end.

[5,3,1,4,2]
Build max-heap: [5,4,1,3,2]
Extract 5 → [4,3,1,2] + [5]
Extract 4 → [3,2,1]   + [4,5]
Extract 3 → [2,1]     + [3,4,5]
Extract 2 → [1]       + [2,3,4,5]
Result: [1,2,3,4,5]

function heapSort(array $arr): array {
    $n = count($arr);

    // Build max-heap (heapify from bottom up)
    for ($i = intdiv($n, 2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }

    // Extract elements from heap one by one
    for ($i = $n - 1; $i > 0; $i--) {
        [$arr[0], $arr[$i]] = [$arr[$i], $arr[0]]; // move root to end
        heapify($arr, $i, 0);                        // re-heapify reduced heap
    }

    return $arr;
}

function heapify(array &$arr, int $n, int $i): void {
    $largest = $i;
    $left    = 2 * $i + 1;
    $right   = 2 * $i + 2;

    if ($left < $n && $arr[$left] > $arr[$largest])  $largest = $left;
    if ($right < $n && $arr[$right] > $arr[$largest]) $largest = $right;

    if ($largest !== $i) {
        [$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
        heapify($arr, $n, $largest);
    }
}

Best	Average	Worst	Space	Stable
O(n log n)	O(n log n)	O(n log n)	O(1)	❌

When to use: Memory-constrained environments, guaranteed O(n log n) with O(1) space.

Counting Sort

Concept: Count frequency of each value. Compute cumulative counts. Place elements in correct position.

Input: [4,2,2,8,3,3,1]
Range: 1–8
Count: [0,1,2,0,1,0,0,0,1]
       [1,2,3,4,5,6,7,8]
Output: [1,2,2,3,3,4,8]

function countingSort(array $arr): array {
    if (empty($arr)) return $arr;

    $max = max($arr);
    $min = min($arr);
    $range = $max - $min + 1;

    $count  = array_fill(0, $range, 0);
    $output = array_fill(0, count($arr), 0);

    // Count occurrences
    foreach ($arr as $val) {
        $count[$val - $min]++;
    }

    // Cumulative count
    for ($i = 1; $i < $range; $i++) {
        $count[$i] += $count[$i - 1];
    }

    // Build output (traverse backwards for stability)
    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $output[--$count[$arr[$i] - $min]] = $arr[$i];
    }

    return $output;
}

Best	Average	Worst	Space	Stable
O(n+k)	O(n+k)	O(n+k)	O(k)	✅

When to use: Integer data, small range (k). E.g., grades 0–100, ages 0–120. Do NOT use when: Range k is very large (e.g., sort numbers up to 1 billion).

Radix Sort

Concept: Sort digit by digit (ones → tens → hundreds) using stable sort at each step.

Input: [170,45,75,90,802,24,2,66]

Sort by 1s: [170,90,802,2,24,45,75,66]
Sort by 10s: [802,2,24,45,66,170,75,90]
Sort by 100s: [2,24,45,66,75,90,170,802]

function radixSort(array $arr): array {
    $max = max($arr);

    for ($exp = 1; intdiv($max, $exp) > 0; $exp *= 10) {
        $arr = countingSortByDigit($arr, $exp);
    }
    return $arr;
}

function countingSortByDigit(array $arr, int $exp): array {
    $n      = count($arr);
    $output = array_fill(0, $n, 0);
    $count  = array_fill(0, 10, 0);

    foreach ($arr as $num) {
        $digit = intdiv($num, $exp) % 10;
        $count[$digit]++;
    }

    for ($i = 1; $i < 10; $i++) {
        $count[$i] += $count[$i - 1];
    }

    for ($i = $n - 1; $i >= 0; $i--) {
        $digit = intdiv($arr[$i], $exp) % 10;
        $output[--$count[$digit]] = $arr[$i];
    }

    return $output;
}

Best	Average	Worst	Space	Stable
O(d×n)	O(d×(n+k))	O(d×(n+k))	O(n+k)	✅

When to use: Large integers, phone numbers, IDs, zip codes.

Bucket Sort

Concept: Distribute elements into buckets. Sort each bucket. Concatenate.

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

    $buckets = array_fill(0, $n, []);

    foreach ($arr as $val) {
        $idx = (int)($val * $n); // assumes values in [0, 1)
        $idx = min($idx, $n - 1);
        $buckets[$idx][] = $val;
    }

    $result = [];
    foreach ($buckets as $bucket) {
        sort($bucket); // sort each bucket
        foreach ($bucket as $val) {
            $result[] = $val;
        }
    }

    return $result;
}

Best	Average	Worst	Space	Stable
O(n+k)	O(n+k)	O(n²)	O(n+k)	✅

When to use: Uniformly distributed floating-point values in [0,1).

Quick Decision Guide (Interview Cheat Sheet)

Input Type?
├── Integers, small range (0–1000)?  →  Counting Sort
├── Integers, large values but few digits?  →  Radix Sort
├── Floats [0,1), uniform distribution?  →  Bucket Sort
├── Nearly sorted / small array?  →  Insertion Sort
├── Need guaranteed O(n log n)?
│   ├── Memory limited?  →  Heap Sort
│   ├── Need stability?  →  Merge Sort
│   └── General purpose?  →  Quick Sort
└── Always works, average fastest:  →  Quick Sort

PHP Built-in Sort (Uses Tim Sort Internally)

// PHP uses Tim Sort (Merge + Insertion hybrid) — O(n log n) guaranteed, stable

$arr = [3, 1, 4, 1, 5, 9, 2, 6];
sort($arr);   // ascending
rsort($arr);  // descending

// Custom comparator
usort($arr, fn($a, $b) => $a <=> $b);  // ascending
usort($arr, fn($a, $b) => $b <=> $a);  // descending

// Laravel sort by column
$users = collect($users)->sortBy('age')->values()->toArray();

Interview Questions — Sorting

Q1. Sort array of 0s, 1s, 2s (Dutch National Flag) `[M][FB]`

Question: Sort [2,0,1,2,1,0,1,2,0] using a single pass, O(1) space.

🧠 How to Approach This

Step 1 — Recognize the pattern:

Only 3 distinct values (0, 1, 2) + O(1) space + single pass = Dutch National Flag algorithm (3-way partition).

Step 2 — Brute force:

Count 0s, 1s, 2s, then overwrite array → O(n) but 2 passes.

Step 3 — Dutch National Flag insight:

Three regions: [0..low-1] = all 0s, [low..mid-1] = all 1s, [high+1..n-1] = all 2s. The middle region [mid..high] is unexplored.

Step 4 — Algorithm:

- arr[mid] == 0: swap with arr[low], low++, mid++ (0 goes to left region)

- arr[mid] == 1: mid++ (1 stays in middle)

- arr[mid] == 2: swap with arr[high], high-- (2 goes to right region; DON'T increment mid — the swapped element needs checking)

Step 5 — Edge cases:

- All same: pointers pass each other quickly, no swaps needed

- Already sorted: mid scans through without swaps

[2,0,1,2,1,0,1,2,0]
 L           H
 M

if arr[mid]==0: swap(low,mid), low++, mid++
if arr[mid]==1: mid++
if arr[mid]==2: swap(mid,high), high--  (don't increment mid!)

function sortColors(array $arr): array {
    $low = 0;
    $mid = 0;
    $high = count($arr) - 1;

    while ($mid <= $high) {
        if ($arr[$mid] === 0) {
            [$arr[$low], $arr[$mid]] = [$arr[$mid], $arr[$low]];
            $low++;
            $mid++;
        } elseif ($arr[$mid] === 1) {
            $mid++;
        } else { // 2
            [$arr[$mid], $arr[$high]] = [$arr[$high], $arr[$mid]];
            $high--;
            // Don't increment $mid — swapped element needs checking
        }
    }
    return $arr;
}

print_r(sortColors([2,0,1,2,1,0,1,2,0]));
// [0,0,0,1,1,1,2,2,2]

Time: O(n) | Space: O(1)

Q2. Find Kth Largest Element `[M][FB]`

Question: Find the k-th largest element in an unsorted array.

🧠 How to Approach This

Step 1 — Simple approach:

Sort descending → take index k-1. O(n log n). Valid in many interviews.

Step 2 — Optimal: Quick Select (O(n) average):

Partial QuickSort — partition like QuickSort, but only recurse into the partition that contains the k-th element. No need to sort both halves.

Step 3 — Key insight:

After one partition, pivot lands at its correct final position. If that position = k (0-indexed), done. If position < k, recurse right. If position > k, recurse left.

Step 4 — Algorithm:

1. target index = n - k (k-th largest = (n-k)-th smallest)

2. partition(arr, left, right) → returns pivot's final index

3. If pivot index = target: return arr[target]

4. Recurse on correct half only

Step 5 — Edge cases:

- k=1: find maximum (pivot always moves to end of searches)

- All same elements: pivot lands in middle every time

// O(n log n) - simple
function kthLargest(array $arr, int $k): int {
    rsort($arr);
    return $arr[$k - 1];
}

// O(n) average - Quick Select
function kthLargestQuickSelect(array $arr, int $k): int {
    return quickSelect($arr, 0, count($arr) - 1, count($arr) - $k);
}

function quickSelect(array &$arr, int $left, int $right, int $k): int {
    if ($left === $right) return $arr[$left];

    $pivotIdx = partition($arr, $left, $right);

    if ($k === $pivotIdx) return $arr[$k];
    if ($k < $pivotIdx)   return quickSelect($arr, $left, $pivotIdx - 1, $k);
    return quickSelect($arr, $pivotIdx + 1, $right, $k);
}

function partition(array &$arr, int $left, int $right): int {
    $pivot = $arr[$right];
    $i = $left;
    for ($j = $left; $j < $right; $j++) {
        if ($arr[$j] <= $pivot) {
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
            $i++;
        }
    }
    [$arr[$i], $arr[$right]] = [$arr[$right], $arr[$i]];
    return $i;
}

echo kthLargest([3,2,1,5,6,4], 2); // 5

Q3. Count Inversions `[H]`

Question: Count pairs (i,j) where i < j but arr[i] > arr[j].

🧠 How to Approach This

Step 1 — Recognize the pattern:

Count inversions = Modified Merge Sort (sort and count at the same time).

Step 2 — Brute force:

Two nested loops check every pair → O(n²). Need O(n log n).

Step 3 — Merge Sort insight:

During the merge step, when right[j] < left[i], ALL remaining elements in left[] are also > right[j] (because left is sorted). So inversions += count(left) - i.

Step 4 — Algorithm:

1. Divide array into halves

2. Recursively count inversions in each half

3. Count cross-inversions during merge step

4. Total = leftCount + rightCount + crossCount

Step 5 — Edge cases:

- Sorted array: 0 inversions

- Reverse sorted: n*(n-1)/2 inversions (maximum)

function countInversions(array $arr): int {
    $count = 0;
    mergeSortCount($arr, $count);
    return $count;
}

function mergeSortCount(array $arr, int &$count): array {
    $n = count($arr);
    if ($n <= 1) return $arr;

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

    return mergeCount($left, $right, $count);
}

function mergeCount(array $left, array $right, int &$count): array {
    $result = [];
    $i = $j = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $count += count($left) - $i; // all remaining left elements form inversions
            $result[] = $right[$j++];
        }
    }

    while ($i < count($left))  $result[] = $left[$i++];
    while ($j < count($right)) $result[] = $right[$j++];

    return $result;
}

echo countInversions([2, 4, 1, 3, 5]); // 3