Sorting Algorithms — Size & Speed Comparison

Size — Memory

Extra space the algorithm needs beyond the input array. Lower is better. Shown as filled pips; solid blue = more memory.

Speed — Time Complexity

Growth rate of operations (comparisons + swaps) as n grows. Green linearithmic or better · amber quadratic · red worst-case blowup.

	Size · Extra Memory	Speed · Time Complexity			Stable?
Algorithm	Space	Best case	Average case	Worst case	Preserves order of equal keys
Bubble Sort adjacent-swap · simple	O(1) — in-place	O(n) with early exit	O(n²)	O(n²)	Yes
Selection Sort min-scan · simple	O(1) — in-place	O(n²)	O(n²)	O(n²)	No
Insertion Sort shift-&-insert · adaptive	O(1) — in-place	O(n) nearly-sorted input	O(n²)	O(n²)	Yes
Merge Sort divide & conquer	O(n) — merge buffer	O(n log n)	O(n log n)	O(n log n)	Yes
Quick Sort partition & recurse	O(log n) avg · O(n) worst	O(n log n)	O(n log n)	O(n²) degenerate pivots	No
Heap Sort binary heap	O(1) — in-place	O(n log n)	O(n log n)	O(n log n)	No
Counting Sort non-comparison · integer	O(n + k) — count array	O(n + k)	O(n + k)	O(n + k)	Yes
Radix Sort digit-wise · LSD	O(n + k) — k = base	O(n · k)	O(n · k)	O(n · k)	Yes

Less · better

More · worse

Fast · linear or linearithmic

OK · quadratic

Slow · worst-case degradation

n — number of elements in the input
k — range of input values (counting sort) or base (radix sort)
Stable algorithms preserve the relative order of elements with equal keys
In-place means the algorithm sorts within the original array using O(1) extra space
Bubble sort's O(n) best case requires the early-exit optimization (terminate on a pass with no swaps)
Quick sort's worst-case behavior is avoided in practice by randomized or median-of-three pivot selection

Insertion Sort — small arrays, nearly-sorted data, or as the base case inside hybrid sorts (Timsort, Introsort)
Merge Sort — large datasets, linked lists, external sorting, or whenever stability is required
Quick Sort — general-purpose in-memory sort; usually fastest in practice with good cache behavior
Heap Sort — priority queues, real-time systems where O(n log n) worst-case is required
Counting / Radix — integer or fixed-width keys with a known, bounded range