At this level sorting is a toolbox, not one algorithm: the shape of the data (binary, three-valued, small range, uniformly distributed, nearly sorted) decides the algorithm, and the partition / merge / counting ideas behind the sorts solve a whole family of problems on their own.

Which algorithm for which input

Situation	Best choice	Why
Binary array (two kinds of values)	one partition pass (two pointers)	`O(n)` time, `O(1)` space, no comparison sort needed
Array of three values (0/1/2)	Dutch national flag	one pass, three regions
Size `n`, values in a small range `k`	counting sort	`Θ(n + k)`, stable
Size `n`, values up to `n²` or `n³`	radix sort (base `n`)	`O(d · n)` with `d = 2` or `3` passes
Uniformly distributed over a range	bucket sort	expected `O(n)` with `k ≈ n` buckets
Memory writes are expensive (flash, EEPROM)	cycle sort	minimum possible writes: each element written once
Only adjacent swaps allowed	bubble sort	it is the only one that moves elements one step at a time
Small `n` (≈ under 16)	insertion sort	tiny constants, adaptive, no recursion
Almost sorted input	insertion sort / Timsort	`O(n + inversions)`
Very little extra memory	heap sort / in-place quick sort	`O(1)` or `O(log n)` auxiliary
Must be stable, general purpose	merge sort / Timsort	`O(n log n)` worst case, stable
Linked list	merge sort	needs no random access; `O(1)` extra space
Data on disk (external sorting)	merge sort (k-way)	sequential reads of sorted runs

The general-purpose comparison sorts are merge sort, heap sort and quick sort — all O(n log n) on average, each with a different weakness (extra memory, cache behaviour, worst case). Real libraries combine them into hybrids:

Library call	Algorithm	Stable?
Python `sorted()`, `list.sort()`	Timsort (merge policy refined to powersort in 3.11+)	yes
Java `Arrays.sort(int[])` (primitives)	dual-pivot quick sort	no (irrelevant for primitives)
Java `Arrays.sort(Object[])`, `Collections.sort`, `List.sort`	Timsort	yes
C++ `std::sort`	introsort	no
C++ `std::stable_sort`	merge sort (buffer) / in-place merge if no memory	yes
C `qsort`	implementation-defined (glibc: merge sort, falling back to quick sort)	not guaranteed
JavaScript `Array.prototype.sort`	Timsort in V8 (stable required since ES2019)	yes

Stable sort with a custom key in each language

A sort is stable when equal keys keep their input order. Sorting students by marks: with a stable sort, two students on 70 stay in the order they were entered. This matters for multi-key sorts (sort by name, then stable-sort by department gives “grouped by department, alphabetical inside”).

Python

students = [("Asha", 80), ("Ravi", 70), ("Meena", 80), ("John", 70), ("Zoe", 90)]
students.sort(key=lambda s: s[1])            # Timsort: stable, equal marks keep input order
for name, marks in students:
    print(name, marks)

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Student { string name; int marks; };

int main() {
    vector<Student> students = {{"Asha", 80}, {"Ravi", 70}, {"Meena", 80}, {"John", 70}, {"Zoe", 90}};
    // std::sort (introsort) is NOT stable — use stable_sort when equal keys must keep their order
    stable_sort(students.begin(), students.end(),
                [](const Student& a, const Student& b) { return a.marks < b.marks; });
    for (const Student& s : students) cout << s.name << " " << s.marks << "\n";
}

Java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    record Student(String name, int marks) {}

    public static void main(String[] args) {
        List<Student> students = new ArrayList<>(List.of(
            new Student("Asha", 80), new Student("Ravi", 70), new Student("Meena", 80),
            new Student("John", 70), new Student("Zoe", 90)));
        students.sort(Comparator.comparingInt(Student::marks));   // Timsort for objects: stable
        for (Student s : students) System.out.println(s.name() + " " + s.marks());
    }
}

JavaScript

const students = [["Asha", 80], ["Ravi", 70], ["Meena", 80], ["John", 70], ["Zoe", 90]];
students.sort((a, b) => a[1] - b[1]);        // stable since ES2019 (V8 uses Timsort)
for (const [name, marks] of students) console.log(name, marks);

Output

Ravi 70
John 70
Asha 80
Meena 80
Zoe 90

Tail call elimination in quick sort

Textbook quick sort recurses twice. The second call is a tail call — nothing happens after it returns — so it can be replaced by a loop that simply updates low and continues. That alone saves one frame per level, but the real win comes from choosing which side to recurse on.

Python

def partition(arr, low, high):            # Lomuto: pivot = arr[high]
    pivot, i = arr[high], low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):           # two recursive calls
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)      # tail call: nothing after it

def quick_sort_tce(arr, low, high):       # tail call replaced by a loop
    while low < high:
        p = partition(arr, low, high)
        quick_sort_tce(arr, low, p - 1)
        low = p + 1                        # "call" on the right part = continue the loop

a = [10, 80, 30, 90, 40, 50, 70]
quick_sort_tce(a, 0, len(a) - 1)
print(*a)

Output

10 30 40 50 70 80 90

Python

depth = max_depth = 0

def partition(arr, low, high):
    pivot, i = arr[high], low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    global depth, max_depth
    depth += 1
    max_depth = max(max_depth, depth)
    while low < high:
        p = partition(arr, low, high)
        if p - low < high - p:              # recurse into the smaller side ...
            quick_sort(arr, low, p - 1)
            low = p + 1                     # ... and loop on the larger one
        else:
            quick_sort(arr, p + 1, high)
            high = p - 1
    depth -= 1

a = list(range(1, 17))                      # already sorted: worst case for arr[high] pivots
quick_sort(a, 0, len(a) - 1)
print("sorted:", *a)
print("max recursion depth:", max_depth)

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int depth = 0, maxDepth = 0;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++)
        if (arr[j] <= pivot) swap(arr[++i], arr[j]);
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    depth++;
    maxDepth = max(maxDepth, depth);
    while (low < high) {
        int p = partition(arr, low, high);
        if (p - low < high - p) {           // recurse into the smaller side ...
            quickSort(arr, low, p - 1);
            low = p + 1;                    // ... and loop on the larger one
        } else {
            quickSort(arr, p + 1, high);
            high = p - 1;
        }
    }
    depth--;
}

int main() {
    vector<int> a(16);
    for (int i = 0; i < 16; i++) a[i] = i + 1;   // already sorted: worst case for arr[high] pivots
    quickSort(a, 0, 15);
    cout << "sorted:";
    for (int x : a) cout << " " << x;
    cout << "\nmax recursion depth: " << maxDepth << "\n";
}

Java

public class Main {
    static int depth = 0, maxDepth = 0;

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high], i = low - 1;
        for (int j = low; j < high; j++)
            if (arr[j] <= pivot) { i++; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
        int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
        return i + 1;
    }

    static void quickSort(int[] arr, int low, int high) {
        depth++;
        maxDepth = Math.max(maxDepth, depth);
        while (low < high) {
            int p = partition(arr, low, high);
            if (p - low < high - p) {       // recurse into the smaller side ...
                quickSort(arr, low, p - 1);
                low = p + 1;                // ... and loop on the larger one
            } else {
                quickSort(arr, p + 1, high);
                high = p - 1;
            }
        }
        depth--;
    }

    public static void main(String[] args) {
        int[] a = new int[16];
        for (int i = 0; i < 16; i++) a[i] = i + 1;   // already sorted: worst case for arr[high] pivots
        quickSort(a, 0, 15);
        StringBuilder sb = new StringBuilder("sorted:");
        for (int x : a) sb.append(' ').append(x);
        System.out.println(sb);
        System.out.println("max recursion depth: " + maxDepth);
    }
}

JavaScript

let depth = 0, maxDepth = 0;

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;
    for (let j = low; j < high; j++)
        if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

function quickSort(arr, low, high) {
    depth++;
    maxDepth = Math.max(maxDepth, depth);
    while (low < high) {
        const p = partition(arr, low, high);
        if (p - low < high - p) {           // recurse into the smaller side ...
            quickSort(arr, low, p - 1);
            low = p + 1;                    // ... and loop on the larger one
        } else {
            quickSort(arr, p + 1, high);
            high = p - 1;
        }
    }
    depth--;
}

const a = Array.from({ length: 16 }, (_, i) => i + 1);   // already sorted: worst case for arr[high] pivots
quickSort(a, 0, 15);
console.log("sorted:", a.join(" "));
console.log("max recursion depth:", maxDepth);

Output

sorted: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
max recursion depth: 2

Time O(n log n) average, O(n²) worst · Space O(log n) stack — guaranteed

Kth smallest element (quickselect)

Python

# Naive: sort everything, then index — O(n log n)
def kth_smallest(arr, k):
    return sorted(arr)[k - 1]

print(kth_smallest([10, 5, 30, 12], 2))
print(kth_smallest([7, 10, 4, 3, 20, 15], 3))

Output

10
7

Python

def partition(arr, low, high):
    pivot, i = arr[high], low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def kth_smallest(arr, k):
    low, high = 0, len(arr) - 1
    while low <= high:
        p = partition(arr, low, high)   # pivot lands at its final sorted index
        if p == k - 1:
            return arr[p]
        if p > k - 1:
            high = p - 1                # answer is on the left
        else:
            low = p + 1                 # answer is on the right
    return -1

for arr, k, label in [([10, 5, 30, 12], 2, "2nd"), ([7, 10, 4, 3, 20, 15], 3, "3rd"), ([7, 10, 4, 3, 20, 15], 4, "4th")]:
    print(f"{label} smallest of [{', '.join(map(str, arr))}] = {kth_smallest(arr[:], k)}")

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++)
        if (arr[j] <= pivot) swap(arr[++i], arr[j]);
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

int kthSmallest(vector<int> arr, int k) {
    int low = 0, high = (int)arr.size() - 1;
    while (low <= high) {
        int p = partition(arr, low, high);   // pivot lands at its final sorted index
        if (p == k - 1) return arr[p];
        if (p > k - 1) high = p - 1;         // answer is on the left
        else low = p + 1;                    // answer is on the right
    }
    return -1;
}

void show(const vector<int>& arr, int k, const string& label) {
    cout << label << " smallest of [";
    for (int i = 0; i < (int)arr.size(); i++) cout << (i ? ", " : "") << arr[i];
    cout << "] = " << kthSmallest(arr, k) << "\n";
}

int main() {
    show({10, 5, 30, 12}, 2, "2nd");
    show({7, 10, 4, 3, 20, 15}, 3, "3rd");
    show({7, 10, 4, 3, 20, 15}, 4, "4th");
}

Java

import java.util.Arrays;

public class Main {
    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high], i = low - 1;
        for (int j = low; j < high; j++)
            if (arr[j] <= pivot) { i++; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
        int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
        return i + 1;
    }

    static int kthSmallest(int[] arr, int k) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int p = partition(arr, low, high);   // pivot lands at its final sorted index
            if (p == k - 1) return arr[p];
            if (p > k - 1) high = p - 1;         // answer is on the left
            else low = p + 1;                    // answer is on the right
        }
        return -1;
    }

    static void show(int[] arr, int k, String label) {
        String list = Arrays.toString(arr);      // "[10, 5, 30, 12]"
        System.out.println(label + " smallest of " + list + " = " + kthSmallest(arr.clone(), k));
    }

    public static void main(String[] args) {
        show(new int[]{10, 5, 30, 12}, 2, "2nd");
        show(new int[]{7, 10, 4, 3, 20, 15}, 3, "3rd");
        show(new int[]{7, 10, 4, 3, 20, 15}, 4, "4th");
    }
}

JavaScript

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;
    for (let j = low; j < high; j++)
        if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

function kthSmallest(arr, k) {
    let low = 0, high = arr.length - 1;
    while (low <= high) {
        const p = partition(arr, low, high);   // pivot lands at its final sorted index
        if (p === k - 1) return arr[p];
        if (p > k - 1) high = p - 1;           // answer is on the left
        else low = p + 1;                      // answer is on the right
    }
    return -1;
}

const show = (arr, k, label) =>
    console.log(`${label} smallest of [${arr.join(", ")}] = ${kthSmallest([...arr], k)}`);

show([10, 5, 30, 12], 2, "2nd");
show([7, 10, 4, 3, 20, 15], 3, "3rd");
show([7, 10, 4, 3, 20, 15], 4, "4th");

Output

2nd smallest of [10, 5, 30, 12] = 10
3rd smallest of [7, 10, 4, 3, 20, 15] = 7
4th smallest of [7, 10, 4, 3, 20, 15] = 10

Time O(n) expected, O(n²) worst · Space O(1)

Minimum difference in an array

Python

def min_diff(arr):
    if len(arr) < 2:
        return "INF"
    arr = sorted(arr)
    best = arr[1] - arr[0]
    for i in range(2, len(arr)):
        best = min(best, arr[i] - arr[i - 1])     # closest pair are sorted neighbours
    return str(best)

for a in ([1, 8, 12, 5, 18], [8, 15], [10]):
    print(f"[{', '.join(map(str, a))}] → {min_diff(a)}")

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string minDiff(vector<int> arr) {
    if (arr.size() < 2) return "INF";
    sort(arr.begin(), arr.end());
    int best = arr[1] - arr[0];
    for (int i = 2; i < (int)arr.size(); i++)
        best = min(best, arr[i] - arr[i - 1]);   // closest pair are sorted neighbours
    return to_string(best);
}

int main() {
    for (vector<int> a : {vector<int>{1, 8, 12, 5, 18}, {8, 15}, {10}}) {
        cout << "[";
        for (int i = 0; i < (int)a.size(); i++) cout << (i ? ", " : "") << a[i];
        cout << "] → " << minDiff(a) << "\n";
    }
}

Java

import java.util.Arrays;

public class Main {
    static String minDiff(int[] arr) {
        if (arr.length < 2) return "INF";
        arr = arr.clone();
        Arrays.sort(arr);
        int best = arr[1] - arr[0];
        for (int i = 2; i < arr.length; i++)
            best = Math.min(best, arr[i] - arr[i - 1]);   // closest pair are sorted neighbours
        return String.valueOf(best);
    }

    public static void main(String[] args) {
        for (int[] a : new int[][]{{1, 8, 12, 5, 18}, {8, 15}, {10}})
            System.out.println(Arrays.toString(a) + " → " + minDiff(a));
    }
}

JavaScript

function minDiff(arr) {
    if (arr.length < 2) return "INF";
    arr = [...arr].sort((a, b) => a - b);          // numeric comparator!
    let best = arr[1] - arr[0];
    for (let i = 2; i < arr.length; i++)
        best = Math.min(best, arr[i] - arr[i - 1]);   // closest pair are sorted neighbours
    return String(best);
}

for (const a of [[1, 8, 12, 5, 18], [8, 15], [10]])
    console.log(`[${a.join(", ")}] → ${minDiff(a)}`);

Output

[1, 8, 12, 5, 18] → 3
[8, 15] → 7
[10] → INF

Time O(n log n) · Space O(1) beyond the sort

Chocolate distribution problem

n packets with the given chocolate counts; m children each get exactly one packet. Minimise the difference between the largest and smallest packet handed out.

Every window of m consecutive sorted values is a candidate

sorted: 2  3  4  7  9  12  56        m = 3
        [2  3  4]              → 4 - 2 = 2   ← minimum
           [3  4  7]           → 7 - 3 = 4
              [4  7  9]        → 9 - 4 = 5
                 [7  9  12]    → 12 - 7 = 5
                    [9  12 56] → 56 - 9 = 47

Python

def min_spread(packets, m):
    if m == 0 or len(packets) == 0:
        return 0
    if len(packets) < m:
        return -1                              # not enough packets
    packets = sorted(packets)
    best = packets[m - 1] - packets[0]
    for i in range(1, len(packets) - m + 1):   # window [i, i + m - 1]
        best = min(best, packets[i + m - 1] - packets[i])
    return best

print(min_spread([7, 3, 2, 4, 9, 12, 56], 3))
print(min_spread([3, 4, 1, 9, 56, 7, 9, 12], 5))

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int minSpread(vector<int> packets, int m) {
    int n = packets.size();
    if (m == 0 || n == 0) return 0;
    if (n < m) return -1;                      // not enough packets
    sort(packets.begin(), packets.end());
    int best = packets[m - 1] - packets[0];
    for (int i = 1; i + m - 1 < n; i++)        // window [i, i + m - 1]
        best = min(best, packets[i + m - 1] - packets[i]);
    return best;
}

int main() {
    cout << minSpread({7, 3, 2, 4, 9, 12, 56}, 3) << "\n";
    cout << minSpread({3, 4, 1, 9, 56, 7, 9, 12}, 5) << "\n";
}

Java

import java.util.Arrays;

public class Main {
    static int minSpread(int[] packets, int m) {
        int n = packets.length;
        if (m == 0 || n == 0) return 0;
        if (n < m) return -1;                  // not enough packets
        packets = packets.clone();
        Arrays.sort(packets);
        int best = packets[m - 1] - packets[0];
        for (int i = 1; i + m - 1 < n; i++)    // window [i, i + m - 1]
            best = Math.min(best, packets[i + m - 1] - packets[i]);
        return best;
    }

    public static void main(String[] args) {
        System.out.println(minSpread(new int[]{7, 3, 2, 4, 9, 12, 56}, 3));
        System.out.println(minSpread(new int[]{3, 4, 1, 9, 56, 7, 9, 12}, 5));
    }
}

JavaScript

function minSpread(packets, m) {
    const n = packets.length;
    if (m === 0 || n === 0) return 0;
    if (n < m) return -1;                      // not enough packets
    packets = [...packets].sort((a, b) => a - b);
    let best = packets[m - 1] - packets[0];
    for (let i = 1; i + m - 1 < n; i++)        // window [i, i + m - 1]
        best = Math.min(best, packets[i + m - 1] - packets[i]);
    return best;
}

console.log(minSpread([7, 3, 2, 4, 9, 12, 56], 3));
console.log(minSpread([3, 4, 1, 9, 56, 7, 9, 12], 5));

Output

2
6

Time O(n log n) · Space O(1) beyond the sort

Sort an array with two types of elements

Three classic variants of the same problem — move every element of one type before every element of the other, in a single pass with O(1) space:

Python

# Naive: copy the "left" type, then the "right" type, into a temporary array — O(n) time but O(n) space
def two_types_naive(arr, is_left):
    temp = [x for x in arr if is_left(x)] + [x for x in arr if not is_left(x)]
    for i in range(len(arr)):
        arr[i] = temp[i]
    return arr

print(*two_types_naive([15, 18, -3, -2], lambda x: x < 0))
print(*two_types_naive([0, 1, 1, 1, 0], lambda x: x == 0))

Output

-3 -2 15 18
0 0 1 1 1

Python

def two_types(arr, is_left):
    i, j = 0, len(arr) - 1
    while i < j:
        while i < j and is_left(arr[i]):        # already on the correct side
            i += 1
        while i < j and not is_left(arr[j]):
            j -= 1
        if i < j:                               # arr[i] is right-type, arr[j] is left-type
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
    return arr

print("negatives first:", *two_types([15, 18, -3, -2], lambda x: x < 0))
print("evens first:", *two_types([15, 14, 13, 12], lambda x: x % 2 == 0))
print("binary:", *two_types([0, 1, 1, 1, 0], lambda x: x == 0))

C++

#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void twoTypes(vector<int>& arr, const function<bool(int)>& isLeft) {
    int i = 0, j = (int)arr.size() - 1;
    while (i < j) {
        while (i < j && isLeft(arr[i])) i++;    // already on the correct side
        while (i < j && !isLeft(arr[j])) j--;
        if (i < j) swap(arr[i++], arr[j--]);    // arr[i] is right-type, arr[j] is left-type
    }
}

void show(const string& label, vector<int> arr, const function<bool(int)>& isLeft) {
    twoTypes(arr, isLeft);
    cout << label << ":";
    for (int x : arr) cout << " " << x;
    cout << "\n";
}

int main() {
    show("negatives first", {15, 18, -3, -2}, [](int x) { return x < 0; });
    show("evens first", {15, 14, 13, 12}, [](int x) { return x % 2 == 0; });
    show("binary", {0, 1, 1, 1, 0}, [](int x) { return x == 0; });
}

Java

import java.util.function.IntPredicate;

public class Main {
    static void twoTypes(int[] arr, IntPredicate isLeft) {
        int i = 0, j = arr.length - 1;
        while (i < j) {
            while (i < j && isLeft.test(arr[i])) i++;    // already on the correct side
            while (i < j && !isLeft.test(arr[j])) j--;
            if (i < j) { int t = arr[i]; arr[i++] = arr[j]; arr[j--] = t; }   // swap misplaced pair
        }
    }

    static void show(String label, int[] arr, IntPredicate isLeft) {
        twoTypes(arr, isLeft);
        StringBuilder sb = new StringBuilder(label + ":");
        for (int x : arr) sb.append(' ').append(x);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        show("negatives first", new int[]{15, 18, -3, -2}, x -> x < 0);
        show("evens first", new int[]{15, 14, 13, 12}, x -> x % 2 == 0);
        show("binary", new int[]{0, 1, 1, 1, 0}, x -> x == 0);
    }
}

JavaScript

function twoTypes(arr, isLeft) {
    let i = 0, j = arr.length - 1;
    while (i < j) {
        while (i < j && isLeft(arr[i])) i++;        // already on the correct side
        while (i < j && !isLeft(arr[j])) j--;
        if (i < j) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; j--; }   // swap misplaced pair
    }
    return arr;
}

console.log("negatives first:", twoTypes([15, 18, -3, -2], (x) => x < 0).join(" "));
console.log("evens first:", twoTypes([15, 14, 13, 12], (x) => x % 2 === 0).join(" "));
console.log("binary:", twoTypes([0, 1, 1, 1, 0], (x) => x === 0).join(" "));

Output

negatives first: -2 -3 18 15
evens first: 12 14 13 15
binary: 0 0 1 1 1

Time O(n) · Space O(1)

Sort an array with three types (Dutch national flag)

Python

# Naive: three passes collecting 0s, then 1s, then 2s — O(n) time, O(n) space
def sort012_naive(arr):
    return [x for x in arr if x == 0] + [x for x in arr if x == 1] + [x for x in arr if x == 2]

print(*sort012_naive([0, 1, 2, 1, 1, 2]))

Output

0 1 1 1 2 2

Dijkstra's three-way partition: one pass, O(1) space

[ small … | middle … | ??? unknown ??? | large … ]
  0      low        mid             high       n-1

arr[mid] < L   → swap(arr[low], arr[mid]); low++; mid++
L ≤ arr[mid] ≤ U → mid++
arr[mid] > U   → swap(arr[mid], arr[high]); high--

One routine, parameterised by the middle range [L, U], solves all three variants: 0/1/2 sorting is L = U = 1, three-way partitioning around a pivot is L = U = pivot, and partitioning around a range is the general case.

Python

def three_way(arr, L, U):
    low, mid, high = 0, 0, len(arr) - 1
    while mid <= high:
        if arr[mid] < L:                           # small → grow the left region
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] > U:                         # large → grow the right region
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1                              # mid stays: new arr[mid] is unexamined
        else:                                      # middle → already in place
            mid += 1
    return arr

print(*three_way([0, 1, 2, 1, 1, 2], 1, 1))         # sort 0s, 1s, 2s
print(*three_way([2, 1, 2, 20, 10, 20, 1], 2, 2))   # partition around pivot 2
print(*three_way([10, 5, 6, 3, 20, 9, 40], 5, 10))  # partition around range [5, 10]

C++

#include <iostream>
#include <vector>
using namespace std;

void threeWay(vector<int>& arr, int L, int U) {
    int low = 0, mid = 0, high = (int)arr.size() - 1;
    while (mid <= high) {
        if (arr[mid] < L) swap(arr[low++], arr[mid++]);     // small → grow the left region
        else if (arr[mid] > U) swap(arr[mid], arr[high--]); // large → grow the right (mid stays)
        else mid++;                                         // middle → already in place
    }
}

void show(vector<int> arr, int L, int U) {
    threeWay(arr, L, U);
    for (int i = 0; i < (int)arr.size(); i++) cout << (i ? " " : "") << arr[i];
    cout << "\n";
}

int main() {
    show({0, 1, 2, 1, 1, 2}, 1, 1);          // sort 0s, 1s, 2s
    show({2, 1, 2, 20, 10, 20, 1}, 2, 2);    // partition around pivot 2
    show({10, 5, 6, 3, 20, 9, 40}, 5, 10);   // partition around range [5, 10]
}

Java

public class Main {
    static void threeWay(int[] arr, int L, int U) {
        int low = 0, mid = 0, high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] < L) {                              // small → grow the left region
                int t = arr[low]; arr[low] = arr[mid]; arr[mid] = t;
                low++; mid++;
            } else if (arr[mid] > U) {                       // large → grow the right (mid stays)
                int t = arr[mid]; arr[mid] = arr[high]; arr[high] = t;
                high--;
            } else {
                mid++;                                       // middle → already in place
            }
        }
    }

    static void show(int[] arr, int L, int U) {
        threeWay(arr, L, U);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) sb.append(i > 0 ? " " : "").append(arr[i]);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        show(new int[]{0, 1, 2, 1, 1, 2}, 1, 1);          // sort 0s, 1s, 2s
        show(new int[]{2, 1, 2, 20, 10, 20, 1}, 2, 2);    // partition around pivot 2
        show(new int[]{10, 5, 6, 3, 20, 9, 40}, 5, 10);   // partition around range [5, 10]
    }
}

JavaScript

function threeWay(arr, L, U) {
    let low = 0, mid = 0, high = arr.length - 1;
    while (mid <= high) {
        if (arr[mid] < L) {                                  // small → grow the left region
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++; mid++;
        } else if (arr[mid] > U) {                           // large → grow the right (mid stays)
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        } else {
            mid++;                                           // middle → already in place
        }
    }
    return arr;
}

console.log(threeWay([0, 1, 2, 1, 1, 2], 1, 1).join(" "));         // sort 0s, 1s, 2s
console.log(threeWay([2, 1, 2, 20, 10, 20, 1], 2, 2).join(" "));   // partition around pivot 2
console.log(threeWay([10, 5, 6, 3, 20, 9, 40], 5, 10).join(" "));  // partition around range [5, 10]

Output

0 1 1 1 2 2
1 1 2 2 20 10 20
3 5 6 10 9 40 20

Time O(n) · Space O(1)

Merge overlapping intervals

Two intervals a and b overlap when a.start <= b.end and b.start <= a.end (they touch or cross). The naive approach repeatedly picks an interval, merges everything that overlaps it and deletes the absorbed ones — up to n passes of O(n²) work.

After sorting, each interval is compared with the last merged one only

sorted:  [1,3] [2,4] [5,7] [6,8]

[1,3]            → start result: [1,3]
[2,4]  2 ≤ 3     → overlaps, extend: [1,4]
[5,7]  5 > 4     → new interval:     [1,4] [5,7]
[6,8]  6 ≤ 7     → overlaps, extend: [1,4] [5,8]

Python

def merge_intervals(intervals):
    intervals.sort(key=lambda iv: iv[0])          # by start
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:                # overlaps the last merged interval
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

for ivs in ([[1, 3], [2, 4], [5, 7], [6, 8]], [[7, 9], [6, 10], [4, 5], [1, 3], [2, 4]]):
    print(" ".join(f"[{s},{e}]" for s, e in merge_intervals(ivs)))

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> mergeIntervals(vector<pair<int, int>> iv) {
    sort(iv.begin(), iv.end());                   // pairs sort by start, then end
    vector<pair<int, int>> merged = {iv[0]};
    for (int i = 1; i < (int)iv.size(); i++) {
        if (iv[i].first <= merged.back().second)  // overlaps the last merged interval
            merged.back().second = max(merged.back().second, iv[i].second);
        else
            merged.push_back(iv[i]);
    }
    return merged;
}

int main() {
    vector<vector<pair<int, int>>> tests = {{{1, 3}, {2, 4}, {5, 7}, {6, 8}},
                                            {{7, 9}, {6, 10}, {4, 5}, {1, 3}, {2, 4}}};
    for (auto& t : tests) {
        auto m = mergeIntervals(t);
        for (int i = 0; i < (int)m.size(); i++)
            cout << (i ? " " : "") << "[" << m[i].first << "," << m[i].second << "]";
        cout << "\n";
    }
}

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static List<int[]> mergeIntervals(int[][] iv) {
        Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0]));   // by start
        List<int[]> merged = new ArrayList<>();
        merged.add(iv[0]);
        for (int i = 1; i < iv.length; i++) {
            int[] last = merged.get(merged.size() - 1);
            if (iv[i][0] <= last[1])                          // overlaps the last merged interval
                last[1] = Math.max(last[1], iv[i][1]);
            else
                merged.add(iv[i]);
        }
        return merged;
    }

    public static void main(String[] args) {
        int[][][] tests = {{{1, 3}, {2, 4}, {5, 7}, {6, 8}}, {{7, 9}, {6, 10}, {4, 5}, {1, 3}, {2, 4}}};
        for (int[][] t : tests) {
            StringBuilder sb = new StringBuilder();
            for (int[] m : mergeIntervals(t))
                sb.append(sb.length() > 0 ? " " : "").append("[").append(m[0]).append(",").append(m[1]).append("]");
            System.out.println(sb);
        }
    }
}

JavaScript

function mergeIntervals(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);            // by start
    const merged = [intervals[0]];
    for (let i = 1; i < intervals.length; i++) {
        const last = merged[merged.length - 1];
        if (intervals[i][0] <= last[1])               // overlaps the last merged interval
            last[1] = Math.max(last[1], intervals[i][1]);
        else
            merged.push(intervals[i]);
    }
    return merged;
}

for (const ivs of [[[1, 3], [2, 4], [5, 7], [6, 8]], [[7, 9], [6, 10], [4, 5], [1, 3], [2, 4]]])
    console.log(mergeIntervals(ivs).map(([s, e]) => `[${s},${e}]`).join(" "));

Output

[1,4] [5,8]
[1,5] [6,10]

Time O(n log n) · Space O(n) for the result (O(1) if merged in place)

Meeting maximum guests

Guest i is present from arrival[i] to departure[i] (times 0000–2359). Find the maximum number of guests present at the same time — the moment to hold a toast. Checking every minute against every guest is O(1440 · n); checking every arrival against every guest is O(n²).

Sweep both sorted arrays like a merge, counting current guests

arrivals:    500  600  700  800
departures:  530  820  830  840

time  500 → +1 (1)   530 → -1 (0)   600 → +1 (1)   700 → +1 (2)
      800 → +1 (3)   820 → -1 (2)   830 → -1 (1)   840 → -1 (0)
maximum = 3

Python

def max_guests(arrival, departure):
    arrival, departure = sorted(arrival), sorted(departure)
    n = len(arrival)
    i, j = 1, 0
    current = best = 1 if n else 0
    while i < n and j < n:
        if arrival[i] <= departure[j]:      # next event is an arrival (ties count as overlap)
            current += 1
            i += 1
        else:                               # next event is a departure
            current -= 1
            j += 1
        best = max(best, current)
    return best

print(max_guests([900, 940], [1000, 1030]))
print(max_guests([800, 700, 600, 500], [840, 820, 830, 530]))

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int maxGuests(vector<int> arrival, vector<int> departure) {
    sort(arrival.begin(), arrival.end());
    sort(departure.begin(), departure.end());
    int n = arrival.size();
    int i = 1, j = 0, current = n ? 1 : 0, best = current;
    while (i < n && j < n) {
        if (arrival[i] <= departure[j]) { current++; i++; }   // arrival (ties count as overlap)
        else { current--; j++; }                               // departure
        best = max(best, current);
    }
    return best;
}

int main() {
    cout << maxGuests({900, 940}, {1000, 1030}) << "\n";
    cout << maxGuests({800, 700, 600, 500}, {840, 820, 830, 530}) << "\n";
}

Java

import java.util.Arrays;

public class Main {
    static int maxGuests(int[] arrival, int[] departure) {
        arrival = arrival.clone(); departure = departure.clone();
        Arrays.sort(arrival);
        Arrays.sort(departure);
        int n = arrival.length;
        int i = 1, j = 0, current = n > 0 ? 1 : 0, best = current;
        while (i < n && j < n) {
            if (arrival[i] <= departure[j]) { current++; i++; }   // arrival (ties count as overlap)
            else { current--; j++; }                               // departure
            best = Math.max(best, current);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxGuests(new int[]{900, 940}, new int[]{1000, 1030}));
        System.out.println(maxGuests(new int[]{800, 700, 600, 500}, new int[]{840, 820, 830, 530}));
    }
}

JavaScript

function maxGuests(arrival, departure) {
    arrival = [...arrival].sort((a, b) => a - b);
    departure = [...departure].sort((a, b) => a - b);
    const n = arrival.length;
    let i = 1, j = 0, current = n ? 1 : 0, best = current;
    while (i < n && j < n) {
        if (arrival[i] <= departure[j]) { current++; i++; }   // arrival (ties count as overlap)
        else { current--; j++; }                               // departure
        best = Math.max(best, current);
    }
    return best;
}

console.log(maxGuests([900, 940], [1000, 1030]));
console.log(maxGuests([800, 700, 600, 500], [840, 820, 830, 530]));

Output

2
3

Time O(n log n) · Space O(1) beyond the sorts

Counting sort

Python

# Simplest form: count, then write each value count[v] times — fine for plain integers
def counting_sort_simple(arr, k):
    count = [0] * k
    for x in arr:
        count[x] += 1
    idx = 0
    for v in range(k):
        for _ in range(count[v]):
            arr[idx] = v
            idx += 1

a = [1, 4, 4, 1, 0, 1]
counting_sort_simple(a, 5)
print(*a)

Output

0 1 1 1 4 4

That version only works when the value is the whole record. To sort students by marks (records with a key) you must move the original objects, which needs the stable formulation:

Prefix sums turn counts into positions; scanning right-to-left keeps equal keys in input order

arr   = 1 4 4 1 0 1          k = 5

count = [1, 3, 0, 0, 2]      how many of each value
prefix= [1, 4, 4, 4, 6]      count[v] = number of elements ≤ v  (= end position of value v)

scan arr from the RIGHT, place each x at output[count[x] - 1], then count[x]--:
  x=1 → output[3]=1, count[1]=3      x=0 → output[0]=0
  x=1 → output[2]=1, count[1]=2      x=1 → output[1]=1
  x=4 → output[5]=4, count[4]=1      x=4 → output[4]=4
output = 0 1 1 1 4 4

Python

def counting_sort(arr, k):
    count = [0] * k
    for x in arr:
        count[x] += 1
    for v in range(1, k):
        count[v] += count[v - 1]          # count[v] = number of elements <= v
    output = [0] * len(arr)
    for x in reversed(arr):               # right-to-left keeps the sort stable
        count[x] -= 1
        output[count[x]] = x
    arr[:] = output

a = [1, 4, 4, 1, 0, 1]
counting_sort(a, 5)
print(*a)

C++

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr, int k) {
    vector<int> count(k, 0);
    for (int x : arr) count[x]++;
    for (int v = 1; v < k; v++) count[v] += count[v - 1];   // count[v] = number of elements <= v
    vector<int> output(arr.size());
    for (int i = (int)arr.size() - 1; i >= 0; i--)          // right-to-left keeps the sort stable
        output[--count[arr[i]]] = arr[i];
    arr = output;
}

int main() {
    vector<int> a = {1, 4, 4, 1, 0, 1};
    countingSort(a, 5);
    for (int i = 0; i < (int)a.size(); i++) cout << (i ? " " : "") << a[i];
    cout << "\n";
}

Java

public class Main {
    static void countingSort(int[] arr, int k) {
        int[] count = new int[k];
        for (int x : arr) count[x]++;
        for (int v = 1; v < k; v++) count[v] += count[v - 1];   // count[v] = number of elements <= v
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--)               // right-to-left keeps the sort stable
            output[--count[arr[i]]] = arr[i];
        System.arraycopy(output, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] a = {1, 4, 4, 1, 0, 1};
        countingSort(a, 5);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; i++) sb.append(i > 0 ? " " : "").append(a[i]);
        System.out.println(sb);
    }
}

JavaScript

function countingSort(arr, k) {
    const count = new Array(k).fill(0);
    for (const x of arr) count[x]++;
    for (let v = 1; v < k; v++) count[v] += count[v - 1];   // count[v] = number of elements <= v
    const output = new Array(arr.length);
    for (let i = arr.length - 1; i >= 0; i--)               // right-to-left keeps the sort stable
        output[--count[arr[i]]] = arr[i];
    for (let i = 0; i < arr.length; i++) arr[i] = output[i];
}

const a = [1, 4, 4, 1, 0, 1];
countingSort(a, 5);
console.log(a.join(" "));

Output

0 1 1 1 4 4

Time Θ(n + k) · Space Θ(n + k)

Python

# Stability in action: sort records by a key, then any range by shifting with min(arr)
def counting_sort_by(items, key, k):
    count = [0] * k
    for it in items:
        count[key(it)] += 1
    for v in range(1, k):
        count[v] += count[v - 1]
    output = [None] * len(items)
    for it in reversed(items):
        count[key(it)] -= 1
        output[count[key(it)]] = it
    return output

students = [("Asha", 3), ("Ravi", 1), ("Meena", 3), ("John", 1), ("Zoe", 2)]
print(counting_sort_by(students, key=lambda s: s[1], k=4))

def counting_sort_any_range(arr):           # values in [min, max] — shift by min
    lo = min(arr)
    return counting_sort_by(arr, key=lambda x: x - lo, k=max(arr) - lo + 1)

print(counting_sort_any_range([1, -2, 4, 4, -1, 1, 0]))

Output

[('Ravi', 1), ('John', 1), ('Zoe', 2), ('Asha', 3), ('Meena', 3)]
[-2, -1, 0, 1, 1, 4, 4]

Not comparison based — it beats the Ω(n log n) lower bound because it exploits the value range.
Stable when written with prefix sums and a right-to-left scan — this is what radix sort relies on.
Not in place: needs the count array and an output array.
Useless when k is much larger than n (sorting five values in 0..10⁹ would allocate a billion counters) — that is where radix sort takes over.

Cycle sort

One cycle of displacements fixes five elements with five writes

arr = 30 40 50 10 20 50       start at cs = 0, item = 30

30 has 2 smaller → goes to index 2, picks up 50
50 has 3 smaller, one equal already placed? no → index 4, picks up 20
20 has 1 smaller → index 1, picks up 40
40 has 3 smaller → index 3, picks up 10
10 has 0 smaller → index 0 = cs → cycle closed

arr = 10 20 30 40 50 50       5 writes for 5 misplaced elements

Python

def cycle_sort(arr):
    writes = 0
    n = len(arr)
    for cs in range(n - 1):
        item = arr[cs]
        pos = cs
        for i in range(cs + 1, n):               # destination = number of smaller elements
            if arr[i] < item:
                pos += 1
        if pos == cs:
            continue                             # already in place
        while item == arr[pos]:                  # skip duplicates already placed
            pos += 1
        arr[pos], item = item, arr[pos]          # write, pick up the displaced element
        writes += 1
        while pos != cs:                         # follow the cycle back to cs
            pos = cs
            for i in range(cs + 1, n):
                if arr[i] < item:
                    pos += 1
            while item == arr[pos]:
                pos += 1
            arr[pos], item = item, arr[pos]
            writes += 1
    return writes

a = [30, 40, 50, 10, 20, 50]
w = cycle_sort(a)
print(*a)
print("writes:", w)

C++

#include <iostream>
#include <vector>
using namespace std;

int cycleSort(vector<int>& arr) {
    int writes = 0, n = arr.size();
    for (int cs = 0; cs < n - 1; cs++) {
        int item = arr[cs], pos = cs;
        for (int i = cs + 1; i < n; i++)         // destination = number of smaller elements
            if (arr[i] < item) pos++;
        if (pos == cs) continue;                 // already in place
        while (item == arr[pos]) pos++;          // skip duplicates already placed
        swap(arr[pos], item); writes++;          // write, pick up the displaced element
        while (pos != cs) {                      // follow the cycle back to cs
            pos = cs;
            for (int i = cs + 1; i < n; i++)
                if (arr[i] < item) pos++;
            while (item == arr[pos]) pos++;
            swap(arr[pos], item); writes++;
        }
    }
    return writes;
}

int main() {
    vector<int> a = {30, 40, 50, 10, 20, 50};
    int w = cycleSort(a);
    for (int i = 0; i < (int)a.size(); i++) cout << (i ? " " : "") << a[i];
    cout << "\nwrites: " << w << "\n";
}

Java

public class Main {
    static int cycleSort(int[] arr) {
        int writes = 0, n = arr.length;
        for (int cs = 0; cs < n - 1; cs++) {
            int item = arr[cs], pos = cs;
            for (int i = cs + 1; i < n; i++)     // destination = number of smaller elements
                if (arr[i] < item) pos++;
            if (pos == cs) continue;             // already in place
            while (item == arr[pos]) pos++;      // skip duplicates already placed
            int t = arr[pos]; arr[pos] = item; item = t; writes++;   // write, pick up displaced
            while (pos != cs) {                  // follow the cycle back to cs
                pos = cs;
                for (int i = cs + 1; i < n; i++)
                    if (arr[i] < item) pos++;
                while (item == arr[pos]) pos++;
                t = arr[pos]; arr[pos] = item; item = t; writes++;
            }
        }
        return writes;
    }

    public static void main(String[] args) {
        int[] a = {30, 40, 50, 10, 20, 50};
        int w = cycleSort(a);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; i++) sb.append(i > 0 ? " " : "").append(a[i]);
        System.out.println(sb);
        System.out.println("writes: " + w);
    }
}

JavaScript

function cycleSort(arr) {
    let writes = 0;
    const n = arr.length;
    for (let cs = 0; cs < n - 1; cs++) {
        let item = arr[cs], pos = cs;
        for (let i = cs + 1; i < n; i++)         // destination = number of smaller elements
            if (arr[i] < item) pos++;
        if (pos === cs) continue;                // already in place
        while (item === arr[pos]) pos++;         // skip duplicates already placed
        [arr[pos], item] = [item, arr[pos]]; writes++;   // write, pick up the displaced element
        while (pos !== cs) {                     // follow the cycle back to cs
            pos = cs;
            for (let i = cs + 1; i < n; i++)
                if (arr[i] < item) pos++;
            while (item === arr[pos]) pos++;
            [arr[pos], item] = [item, arr[pos]]; writes++;
        }
    }
    return writes;
}

const a = [30, 40, 50, 10, 20, 50];
const w = cycleSort(a);
console.log(a.join(" "));
console.log("writes:", w);

Output

10 20 30 40 50 50
writes: 5

Time O(n²) · Space O(1)

Worst and average case O(n²) comparisons — never use it for speed.
At most n - 1 writes in total, versus up to O(n²) for insertion or bubble sort.
In place, not stable.
The number of writes equals the minimum number of swaps needed to sort the array — the standard way to solve that interview question. When the values are a permutation of 0..n-1, the destination of x is simply x, no counting needed, and the whole sort becomes O(n).

Radix sort

Three stable passes (one per digit) — each pass preserves the order established by the previous ones

write with leading zeros:   319 212 006 008 100 050

stable sort by units digit:     100 050 212 006 008 319
stable sort by tens digit:      100 006 008 212 319 050
stable sort by hundreds digit:  006 008 050 100 212 319

Python

def counting_sort_by_digit(arr, exp):
    output = [0] * len(arr)
    count = [0] * 10
    for x in arr:
        count[(x // exp) % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]
    for x in reversed(arr):                    # stable
        d = (x // exp) % 10
        count[d] -= 1
        output[count[d]] = x
    arr[:] = output

def radix_sort(arr):
    mx = max(arr)
    exp = 1
    while mx // exp > 0:                       # one pass per digit of the maximum
        counting_sort_by_digit(arr, exp)
        print(f"after pass exp={exp}:", *arr)
        exp *= 10

radix_sort([319, 212, 6, 8, 100, 50])

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void countingSortByDigit(vector<int>& arr, int exp) {
    vector<int> output(arr.size()), count(10, 0);
    for (int x : arr) count[(x / exp) % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d - 1];
    for (int i = (int)arr.size() - 1; i >= 0; i--)   // stable
        output[--count[(arr[i] / exp) % 10]] = arr[i];
    arr = output;
}

void radixSort(vector<int>& arr) {
    int mx = *max_element(arr.begin(), arr.end());
    for (int exp = 1; mx / exp > 0; exp *= 10) {   // one pass per digit of the maximum
        countingSortByDigit(arr, exp);
        cout << "after pass exp=" << exp << ":";
        for (int x : arr) cout << " " << x;
        cout << "\n";
    }
}

int main() {
    vector<int> a = {319, 212, 6, 8, 100, 50};
    radixSort(a);
}

Java

public class Main {
    static void countingSortByDigit(int[] arr, int exp) {
        int[] output = new int[arr.length], count = new int[10];
        for (int x : arr) count[(x / exp) % 10]++;
        for (int d = 1; d < 10; d++) count[d] += count[d - 1];
        for (int i = arr.length - 1; i >= 0; i--)        // stable
            output[--count[(arr[i] / exp) % 10]] = arr[i];
        System.arraycopy(output, 0, arr, 0, arr.length);
    }

    static void radixSort(int[] arr) {
        int mx = 0;
        for (int x : arr) mx = Math.max(mx, x);
        for (int exp = 1; mx / exp > 0; exp *= 10) {     // one pass per digit of the maximum
            countingSortByDigit(arr, exp);
            StringBuilder sb = new StringBuilder("after pass exp=" + exp + ":");
            for (int x : arr) sb.append(' ').append(x);
            System.out.println(sb);
        }
    }

    public static void main(String[] args) {
        radixSort(new int[]{319, 212, 6, 8, 100, 50});
    }
}

JavaScript

function countingSortByDigit(arr, exp) {
    const output = new Array(arr.length), count = new Array(10).fill(0);
    for (const x of arr) count[Math.floor(x / exp) % 10]++;
    for (let d = 1; d < 10; d++) count[d] += count[d - 1];
    for (let i = arr.length - 1; i >= 0; i--)            // stable
        output[--count[Math.floor(arr[i] / exp) % 10]] = arr[i];
    for (let i = 0; i < arr.length; i++) arr[i] = output[i];
}

function radixSort(arr) {
    const mx = Math.max(...arr);
    for (let exp = 1; Math.floor(mx / exp) > 0; exp *= 10) {   // one pass per digit of the maximum
        countingSortByDigit(arr, exp);
        console.log(`after pass exp=${exp}:`, arr.join(" "));
    }
}

radixSort([319, 212, 6, 8, 100, 50]);

Output

after pass exp=1: 100 50 212 6 8 319
after pass exp=10: 100 6 8 212 319 50
after pass exp=100: 6 8 50 100 212 319

Time O(d · (n + b)), b = base · Space O(n + b)

Bucket sort

Typical inputs: integers uniformly spread over 1..10⁸ (too wide for counting sort, too many digits for radix), or floating-point numbers uniformly spread in [0, 1) where the bucket index is simply floor(k · x).

Scatter → sort buckets → gather

Scatter (bucket = 5 * x / 100):           Sort each bucket:
  bucket 0 (00-19): 18                       18
  bucket 1 (20-39): 20                       20
  bucket 2 (40-59):                          (empty)
  bucket 3 (60-79): 70 75 60                 60 70 75
  bucket 4 (80-99): 88 85 95 82              82 85 88 95

Gather: 18 20 60 70 75 82 85 88 95

Python

def bucket_sort(arr, k):
    rs = max(arr) + 1                          # values lie in [0, rs)
    buckets = [[] for _ in range(k)]
    for x in arr:
        buckets[(k * x) // rs].append(x)       # scatter
    for i, b in enumerate(buckets):
        print(f"bucket {i}:", *b)
    idx = 0
    for b in buckets:
        b.sort()                               # sort each bucket (small → cheap)
        for x in b:                            # gather
            arr[idx] = x
            idx += 1

a = [20, 88, 70, 85, 75, 95, 18, 82, 60]
bucket_sort(a, 5)
print("sorted:", *a)

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void bucketSort(vector<int>& arr, int k) {
    int rs = *max_element(arr.begin(), arr.end()) + 1;   // values lie in [0, rs)
    vector<vector<int>> buckets(k);
    for (int x : arr) buckets[(k * x) / rs].push_back(x);   // scatter
    for (int i = 0; i < k; i++) {
        cout << "bucket " << i << ":";
        for (int x : buckets[i]) cout << " " << x;
        cout << "\n";
    }
    int idx = 0;
    for (auto& b : buckets) {
        sort(b.begin(), b.end());                        // sort each bucket (small → cheap)
        for (int x : b) arr[idx++] = x;                  // gather
    }
}

int main() {
    vector<int> a = {20, 88, 70, 85, 75, 95, 18, 82, 60};
    bucketSort(a, 5);
    cout << "sorted:";
    for (int x : a) cout << " " << x;
    cout << "\n";
}

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static void bucketSort(int[] arr, int k) {
        int rs = 0;
        for (int x : arr) rs = Math.max(rs, x);
        rs++;                                            // values lie in [0, rs)
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < k; i++) buckets.add(new ArrayList<>());
        for (int x : arr) buckets.get((k * x) / rs).add(x);   // scatter
        for (int i = 0; i < k; i++) {
            StringBuilder sb = new StringBuilder("bucket " + i + ":");
            for (int x : buckets.get(i)) sb.append(' ').append(x);
            System.out.println(sb);
        }
        int idx = 0;
        for (List<Integer> b : buckets) {
            Collections.sort(b);                         // sort each bucket (small → cheap)
            for (int x : b) arr[idx++] = x;              // gather
        }
    }

    public static void main(String[] args) {
        int[] a = {20, 88, 70, 85, 75, 95, 18, 82, 60};
        bucketSort(a, 5);
        StringBuilder sb = new StringBuilder("sorted:");
        for (int x : a) sb.append(' ').append(x);
        System.out.println(sb);
    }
}

JavaScript

function bucketSort(arr, k) {
    const rs = Math.max(...arr) + 1;               // values lie in [0, rs)
    const buckets = Array.from({ length: k }, () => []);
    for (const x of arr) buckets[Math.floor((k * x) / rs)].push(x);   // scatter
    buckets.forEach((b, i) => console.log(`bucket ${i}:${b.map((x) => " " + x).join("")}`));
    let idx = 0;
    for (const b of buckets) {
        b.sort((x, y) => x - y);                   // sort each bucket (small → cheap)
        for (const x of b) arr[idx++] = x;         // gather
    }
}

const a = [20, 88, 70, 85, 75, 95, 18, 82, 60];
bucketSort(a, 5);
console.log("sorted:", a.join(" "));

Output

bucket 0: 18
bucket 1: 20
bucket 2:
bucket 3: 70 75 60
bucket 4: 88 85 95 82
sorted: 18 20 60 70 75 82 85 88 95

Time O(n + k) expected, O(n log n) worst · Space O(n + k)

Comparison of all sorting algorithms

Algorithm	Best	Average	Worst	Space	Stable	In place	Notes
Bubble	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	yes	yes	adjacent swaps only
Selection	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	no	yes	`O(n)` swaps
Insertion	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	yes	yes	best for small / nearly sorted
Merge	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	yes	no	linked lists, external sort
Quick (Lomuto/Hoare)	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`*	no	yes	fastest in practice; *with smaller-side recursion
Heap	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	no	yes	poor cache behaviour
Counting	`Θ(n + k)`	`Θ(n + k)`	`Θ(n + k)`	`O(n + k)`	yes	no	small integer range
Radix (LSD)	`O(d(n + b))`	`O(d(n + b))`	`O(d(n + b))`	`O(n + b)`	yes	no	fixed-width keys
Bucket	`O(n + k)`	`O(n + k)`	`O(n log n)`	`O(n + k)`	yes*	no	uniform data; *if inner sort is stable
Cycle	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	no	yes	minimum writes
Timsort	`O(n)`	`O(n log n)`	`O(n log n)`	`O(n)`	yes	no	Python, Java objects, V8
Introsort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(log n)`	no	yes	C++ `std::sort`

Any comparison sort needs Ω(n log n) comparisons in the worst case — counting, radix and bucket sort escape this by not comparing.

Interview Q&A

Why do libraries use hybrid algorithms instead of plain quick sort or merge sort?

Quickselect vs a heap for the kth smallest — when is each better?

How can you sort in O(n)? Doesn't the lower bound forbid it?

Why is the right-to-left scan needed for counting sort to be stable, and why does radix sort need stability?

Explain tail call elimination in quick sort. Does it fix the O(n²) worst case?

Minimum number of swaps to sort an array — which sorting idea applies?