Best Case

Average Case

Worst Case

Notes (what input patterns trigger cases)

Auxiliary Space (extra memory)

In-place or Not

Recursion Stack (if applicable)

Stable (keeps equal keys’ relative order)

Unstable

Adaptive (faster on nearly-sorted data)

Not adaptive

Small vs large datasets

Nearly-sorted data

Memory constraints

Need for stability

External sorting (disk-based)

Repeatedly swap adjacent out-of-order elements; largest “bubbles” to the end each pass

Best: O(n)

Average: O(n^2)

Worst: O(n^2)

Auxiliary: O(1)

In-place: Yes

Stable (adjacent swaps preserve equal elements’ order)

Yes (with early-exit flag)

Very simple; easy to implement and teach

Works well only for very small or almost-sorted arrays (with optimization)

Too slow for medium/large n

Educational purposes, tiny arrays, nearly sorted with early exit

Repeatedly select the minimum (or maximum) element from the unsorted part and swap into position

Best: O(n^2)

Average: O(n^2)

Worst: O(n^2)

Auxiliary: O(1)

In-place: Yes

Unstable (swap can move equal elements past each other)

Stable variant exists but typically requires extra shifts (may affect performance)

No (work does not reduce for nearly sorted input)

Minimal number of swaps: O(n) swaps

Predictable performance

Still O(n^2) comparisons; slow for large n

When writes/swaps are costly (e.g., flash memory) and n is small

Build a sorted prefix; insert each new element into correct position by shifting larger elements right

Best: O(n)

Average: O(n^2)

Worst: O(n^2)

Auxiliary: O(1)

In-place: Yes

Stable (when inserting by shifting rather than swapping past equals)

Yes (excellent on nearly sorted data; running time ~ O(n + inversions))

Fast for small n and nearly sorted data

Simple and stable

Online (can sort as data arrives)

Quadratic time on random/reverse data for large n

Small arrays; nearly sorted inputs

Used as “base case” inside hybrid sorts (e.g., TimSort, IntroSort implementations often switch for small partitions)

Generalized insertion sort using gaps; perform gapped insertion sorts with decreasing gaps

Best: varies (often better than O(n^2) in practice)

Average: commonly ~ O(n^1.3) to O(n^1.5) (depends on gaps)

Worst: can be O(n^2) for some sequences

Auxiliary: O(1)

In-place: Yes

Unstable (far-apart moves can reorder equals)

Partially (often benefits from some presortedness)

Practical improvement over insertion sort without extra memory

Good for medium-size arrays

Complexity depends on chosen gap sequence; not stable

In-place sorting where extra memory is constrained and n is moderate

Divide array, sort halves recursively, merge two sorted halves

Best: O(n log n)

Average: O(n log n)

Worst: O(n log n)

Auxiliary: O(n) for merging arrays (typical array implementation)

In-place: No (typical); in-place variants exist but are complex and slower in practice

Recursion stack: O(log n)

Stable (if merge favors left element when equal)

Not inherently adaptive (still splits/merges); can benefit slightly from runs if implemented accordingly

Predictable O(n log n)

Stable; good for linked lists (can be O(1) extra space with pointer manipulations)

Good for external sorting (disk), because merging is sequential I/O friendly

Extra memory O(n) for arrays

Need stability with guaranteed O(n log n)

Sorting linked lists

External sorting / very large datasets on disk

Partition around a pivot; recursively sort partitions

Best: O(n log n)

Average: O(n log n)

Worst: O(n^2)

Auxiliary: O(1) (partitioning is in-place)

Recursion stack: O(log n) average, O(n) worst

In-place: Yes (typical in-place partition)

Unstable (partition swaps can reorder equals)

Stable variants exist but usually require extra memory

Not adaptive by default

Randomization reduces probability of worst-case

3-way partitioning (Dutch National Flag) improves performance with many duplicates

Tail recursion elimination / iterative stack can reduce stack usage

Excellent cache locality; often fastest in practice for in-memory arrays

Low constant factors

Worst-case O(n^2) unless mitigated (randomization, introspection)

Unstable

General-purpose in-memory sorting when stability not required; often combined with safeguards (IntroSort)

Build a heap; repeatedly extract max/min and place into final position

Best: O(n log n)

Average: O(n log n)

Worst: O(n log n)

Auxiliary: O(1)

In-place: Yes

Unstable

No

Guaranteed O(n log n) worst-case

In-place with O(1) extra memory

Usually slower than quicksort in practice due to cache behavior

Unstable

When worst-case guarantees and low memory matter

Used inside IntroSort as fallback to avoid quicksort worst-case

Count occurrences of each key in a limited integer range; compute prefix sums to place elements

Best/Average/Worst: O(n + k)

Auxiliary: O(n + k) (output + counts) or O(k) plus in-place-like output handling depending on implementation

In-place: No (typical stable version uses output array)

Stable (when placing elements using prefix sums from right to left)

Not relevant in same way; depends on k, not presortedness

Linear-time when k is not much larger than n

Stable; good building block for radix sort

Requires integer keys / mappable to small range; memory heavy if k is large

Sorting grades, IDs, small-range integers

Preprocessing step for radix sort

Sort by digits/bytes from least significant to most (LSD) or vice versa (MSD) using a stable sub-sort (often counting sort)

Best/Average/Worst: O(d * (n + b))

Auxiliary: often O(n + b) (for stable counting per pass)

In-place: Typically no (common implementations use extra buffers)

Stable (if each digit-pass sort is stable)

Not primarily; performance depends on d and base

Can be near-linear for fixed-width integers/strings

Predictable performance independent of comparisons

Extra memory; requires fixed-length or well-defined digit representation

Sorting 32-bit/64-bit integers

Sorting strings with bounded length (with careful choice of MSD/LSD)

Distribute elements into buckets based on value ranges; sort each bucket (often insertion sort); concatenate

Best: O(n) (uniform distribution, balanced buckets, simple per-bucket sorting)

Average: O(n + k + sum sort(bucket_i))

Worst: O(n^2)

Auxiliary: O(n + k) (buckets)

In-place: No (typical)

Depends on bucket insertion and inner sort; can be stable

Depends on inner sort and distribution

Very fast for uniformly distributed floating-point numbers in [0,1) or known ranges

Sensitive to distribution; extra memory

Data known to be uniformly distributed over a range

Identify naturally occurring runs; use insertion sort on small runs; merge runs with invariants

Best: O(n)

Average: O(n log n)

Worst: O(n log n)

Auxiliary: O(n) worst-case (often less in practice depending on run structure)

Stable

Highly adaptive (designed for real-world partially ordered data)

Excellent real-world performance; stable; exploits existing order

More complex; extra memory for merges

Default sort in Python and Java (object sorting); when stability + real-world performance matter

Start with quicksort; if recursion depth exceeds limit, switch to heap sort; use insertion sort for small partitions

Best/Average: O(n log n)

Worst: O(n log n) (due to heap sort fallback)

Auxiliary: O(1) + recursion stack O(log n)

In-place: Yes (typical)

Unstable (inherits from quicksort/heap sort)

Not specifically; aims for robust worst-case

Quicksort speed with worst-case guarantee

Widely used in C++ std::sort

Unstable

General-purpose in-place sorting with worst-case guarantees