Lesson 1 · Core algorithms

Sorting Algorithms: Methods and Performance

Sorting exposes order that makes later work easier. The right algorithm depends on input size and shape, key range, stability requirements, memory limits, and worst-case guarantees.

The properties that matter

A stable sort preserves the original relative order of equal keys, which matters when records have already been sorted by a secondary field. An in-place algorithm uses little auxiliary memory, though the exact definition may allow recursion stack space.

Also distinguish worst-case, average, and adaptive behavior. A production choice is a bundle of guarantees, not just one Big-O label.

Stable versus unstable
In-place versus auxiliary buffer
Worst-case versus expected time
Adaptive behavior on existing order

Quadratic sorts still have a role

Insertion sort grows a sorted prefix and inserts the next element by shifting larger values. It is O(n²) in the worst case but fast for small or nearly sorted inputs and often appears as the base case inside hybrid sorts.

Selection sort minimizes writes but still performs quadratic comparisons. Bubble sort is mainly educational; repeated adjacent swaps rarely make it a practical default.

Insertion sort is stable and adaptive
Selection sort performs O(n) swaps
Small partitions favor simple tight loops

Key reference

Terms, operations, and practical uses

Sorting properties

StableEqual keys retain their original relative order.
In placeThe algorithm uses only a small amount of auxiliary storage beyond the input.
AdaptiveExisting order reduces the amount of work performed.

Comparison methods

Insertion sortPlaces each new item into an already sorted prefix.
Merge sortSorts smaller halves and combines them through a linear merge.
QuicksortPartitions values around a pivot, then sorts the resulting regions.
HeapsortRepeatedly removes an extreme value from a binary heap.

Analysis

Comparison lower boundA general comparison sort requires Ω(N log N) comparisons in the worst case.
Key rangeCounting and radix methods can avoid that bound when keys expose additional bounded structure.
Nearly sorted inputCan make insertion-based methods far cheaper than their worst case.

Code example

Sort with insertion sort

def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1
        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1
        values[j + 1] = current
    return values
print(insertion_sort([5, 2, 4, 1]))

void insertionSort(vector<int>& values) {
    for (int i = 1; i < values.size(); ++i) {
        int current = values[i];
        int j = i - 1;
        while (j >= 0 && values[j] > current) {
            values[j + 1] = values[j];
            --j;
        }
        values[j + 1] = current;
    }
}

static void insertionSort(int[] values) {
    for (int i = 1; i < values.length; i++) {
        int current = values[i];
        int j = i - 1;
        while (j >= 0 && values[j] > current) {
            values[j + 1] = values[j];
            j--;
        }
        values[j + 1] = current;
    }
}

Input[5, 2, 4, 1]

Output[1, 2, 4, 5]

Example

Run the example step by step

Output

Merge, quick, and heap

Merge sort guarantees O(n log n), is naturally stable, and uses a merge buffer for arrays. Quicksort partitions around a pivot and is fast in practice, but poor pivots can produce O(n²) unless randomized or guarded.

Heapsort guarantees O(n log n) in place but is usually less cache-friendly. Many standard libraries combine strategies to capture strong practical and worst-case behavior.

Merge: stable, predictable, extra array space
Quick: excellent locality, expected O(n log n)
Heap: in-place worst-case O(n log n)

Sorting without comparisons

Counting sort uses a bounded integer key range, while radix sort processes digits or chunks. These methods can beat the comparison lower bound because they use information beyond pairwise comparisons.

Their complexity depends on range or digit width. An O(n + k) algorithm is unattractive when k is enormous relative to n, so include the representation parameters in the analysis.

Counting sort for compact key ranges
Radix sort for fixed-width keys
Bucket methods depend on distribution assumptions