Comprehensive Sorting Algorithms — Detailed Notes

**Scope:** This document covers sorting algorithms from

basics to advanced. For each algorithm you'll find: idea,
detailed explanation, pseudocode, time complexity
(best/average/worst) with derivations, space complexity,
stability, variations, and example walkthroughs. --- ## Table
of Contents 1. Introduction & Lower Bound for Comparison
Sorts 2. Summary Table (quick reference) 3. Elementary sorts
- Bubble Sort - Selection Sort - Insertion Sort 4. Shell Sort 5.
Merge Sort (top-down and bottom-up) 6. Quick Sort (Lomuto,
Hoare, randomized, 3-way) 7. Heap Sort 8. Non-comparison
sorts - Counting Sort - Radix Sort (LSD and MSD) - Bucket
Sort 9. Hybrid & Practical Algorithms - IntroSort - TimSort 10.
When to use which sort (practical guidance) 11. Appendix:
Recurrence solving and Master Theorem sketches 12.
References & further reading --- ## 1. Introduction & Lower
Bound for Comparison Sorts **Problem statement.** Given an
array of `n` items (numbers or keys), arrange them in
non-decreasing order. **Comparison sorts vs
non-comparison sorts.** A comparison sort determines order
only by pairwise comparisons of elements. Non-comparison
sorts (counting, radix, bucket) exploit structure of keys
(integers with limited range, digits, etc.). **Lower bound for
comparison sorts (sketch).** Any comparison sort can be
modeled by a decision tree where each internal node is a
binary comparison and leaves represent permutations of the
input. There are `n!` possible permutations, so the decision
tree must have at least `n!` leaves. If a binary tree has height
`h`, it has at most `2^h` leaves, so `2^h >= n!` ⇒ `h >=
log2(n!)`. Using Stirling's approximation: `log2(n!) = Θ(n log
n)`. Therefore any comparison sort must perform Ω(n log n)
comparisons in the worst case. So **comparison sorts** have
a theoretical lower bound of **Ω(n log n)** time (worst-case),
hence `O(n log n)` is optimal among comparison sorts. --- ##
2. Summary Table (quick reference) | Algorithm | Best |
Average | Worst | Space | Stable | Notes |
|---|---:|---:|---:|---:|---|---| | Bubble Sort | O(n) | O(n^2) | O(n^2) |
O(1) | Yes | Educational only | | Selection Sort | O(n^2) |
O(n^2) | O(n^2) | O(1) | No | Minimal swaps | | Insertion Sort |
O(n) | O(n^2) | O(n^2) | O(1) | Yes | Good for
small/mostly-sorted | | Shell Sort | depends | depends |
depends | O(1) | No | Gap sequence matters | | Merge Sort |
O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Stable,
predictable | | Quick Sort | O(n log n) | O(n log n) | O(n^2) |
O(log n) avg | No | Fast in practice; introsort avoids
worst-case | | Heap Sort | O(n log n) | O(n log n) | O(n log n) |
O(1) | No | In-place, predictable worst-case | | Counting Sort |
O(n + k) | O(n + k) | O(n + k) | O(k + n) | Yes | k = range size | |
Radix Sort | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) |
Stable (if inner stable) | d digits, b base | | Bucket Sort | O(n +
k) avg | O(n + k) | O(n^2) worst | O(n + k) | Depends | Assumes
uniform distribution | | IntroSort | O(n log n) | O(n log n) | O(n
log n) | O(log n) | Depends | std::sort in many libraries | |
TimSort | O(n) best | O(n log n) | O(n log n) | O(n) | Yes |
Python/Java stable hybrid | --- ## 3. Elementary sorts ### 3.1
Bubble Sort **Idea.** Repeatedly scan the array, swapping
adjacent elements that are out of order. After each full pass
the largest remaining element "bubbles" to the end.
**Pseudocode (optimized):** ``` for (i = 0; i < n-1; ++i) {
swapped = false for (j = 0; j < n-1-i; ++j) { if (A[j] > A[j+1]) {
swap(A[j], A[j+1]); swapped = true } } if (!swapped) break } ```
**Time complexity derivation:** - Worst/average: Without the
early-stop optimization, number of comparisons is (n-1) +
(n-2) + ... + 1 = n(n-1)/2 = Θ(n^2). Number of swaps in
worst-case is also Θ(n^2). - Best: If the array already sorted,
the optimized version detects no swaps and completes in
O(n) (single pass). **Space:** O(1). Stable. **When to use:**
Practically none — educational or for tiny arrays in exercises.
### 3.2 Selection Sort **Idea.** Repeatedly select the minimal
(or maximal) remaining element and place it at the front (or
back). **Pseudocode:** ``` for (i = 0; i < n-1; ++i) { minIdx = i
for (j = i+1; j < n; ++j) if (A[j] < A[minIdx]) minIdx = j swap(A[i],
A[minIdx]) } ``` **Complexity derivation:** - Comparisons:
(n-1) + (n-2) + ... + 1 = Θ(n^2) in all cases → best=avg=worst
Θ(n^2). - Swaps: Only n-1 swaps, which is useful when swaps
are expensive. **Space:** O(1). Not stable by default (but can
be made stable at extra cost). **When to use:** Simple and
predictable, but rarely used in practice for large n. ### 3.3
Insertion Sort **Idea.** Build the final sorted array one
element at a time by inserting each new element into its
correct position among previously sorted elements (like
sorting playing cards in your hand). **Pseudocode:** ``` for (i
= 1; i < n; ++i) { key = A[i] j = i - 1 while (j >= 0 and A[j] > key) {
A[j+1] = A[j] j-- } A[j+1] = key } ``` **Complexity derivation:** -
Worst-case (reverse order): For each i, shift i elements ⇒
comparisons/shifts ~ 1 + 2 + ... + (n-1) = Θ(n^2). - Best-case
(already sorted): Each insertion checks once ⇒ Θ(n)
comparisons and Θ(1) shifts. - Average: On random input
average number of shifts is about n^2/4 → Θ(n^2). **Space:**
O(1). Stable. **When to use:** Great for small arrays or
nearly-sorted arrays. Often used as the base-case sorter in
hybrids (e.g., Timsort, introsort) for subarrays of size ≤ 16–32.
--- ## 4. Shell Sort **Idea.** Generalization of insertion sort:
perform insertion sort on elements separated by a gap `g`,
decreasing `g` over iterations until it becomes 1. Early passes
move elements closer to their final position, reducing the
cost of the final insertion sort. **Pseudocode (high-level):** ```
gaps = choose_gap_sequence(n) for gap in gaps: for i = gap
to n-1: temp = A[i] j = i while j >= gap and A[j - gap] > temp:
A[j] = A[j - gap] j -= gap A[j] = temp ``` **Gap sequences and
complexity:** - Complexity depends on gap sequence. -
Original Shell sequence (`n/2, n/4, ...`) yields worst-case
O(n^2). - Pratt, Ciura, Sedgewick sequences improve
performance; with good sequences complexity can be as low
as `O(n^{4/3})` or `O(n^{3/2})` for some choices. **Space:**
O(1). Not stable. **When to use:** Simple in-place
improvement over insertion sort. Good in practice for
medium-size arrays when simple and low-memory. --- ## 5.
Merge Sort **Idea.** Divide-and-conquer: split the array into
two halves, recursively sort each half, then merge the sorted
halves. **Top-down recursive pseudocode:** ``` mergesort(A,
left, right): if left >= right: return mid = (left + right) / 2
mergesort(A, left, mid) mergesort(A, mid+1, right) merge(A,
left, mid, right) // linear-time merge using temp array ```
**Merge step (linear time):** - Use two pointers i (left half) and
j (right half), copy smaller element into temp and advance
pointer. After one half is exhausted copy remainder.
**Complexity derivation (recurrence):** - Let T(n) be time to
sort n elements. We split into two halves of size n/2 and
merge in Θ(n) time. - Recurrence: `T(n) = 2 T(n/2) + cn`. - Solve
by Master Theorem: a = 2, b = 2 → n^{log_b a} = n^{1} = n.
Since f(n) = Θ(n), T(n) = Θ(n log n). - **Therefore** best =
average = worst = Θ(n log n) (recurrence deterministic
regardless of input ordering). **Space:** Θ(n) auxiliary (for
merging). There are in-place merge variants but they're
complex and slower. **Stability:** Stable by default (if merge
copies equal keys from left before right). **Bottom-up
(iterative) merge sort:** start by merging runs of size 1, then
2, then 4, doubling each time. Same complexity. **When to
use:** Stable, predictable time. Good for linked lists (merge
sort on lists is O(1) space for merging because splicing is
O(1)) and external sorting (merge of sorted runs on disk).
**Example Walkthrough:** - Sort `[5,2,3,1]` → split `[5,2]` &
`[3,1]` → sort `[5,2]` → `[2,5]` and `[1,3]` → merge `[1,2,3,5]`. ---
## 6. Quick Sort **Idea.** Pick a pivot, partition array into
elements less than pivot and greater than pivot, recursively
sort the partitions. **Partition (Lomuto) pseudocode
(simple):** ``` partition(A, low, high): pivot = A[high] i = low for
j = low to high-1: if A[j] <= pivot: swap(A[i], A[j]) i++ swap(A[i],
A[high]) return i // pivot final index ``` **Hoare partition (often
faster, different invariants) exists too.** **Randomized
quicksort:** choose pivot randomly (swap with A[high] first).
This avoids pathological inputs. **Complexity:** -
**Worst-case:** O(n^2) when pivot choices are extremely
unbalanced (e.g., sorted input and pivot = first or last element
repeatedly). The recurrence becomes `T(n) = T(n-1) + Θ(n)` →
Θ(n^2). - **Average-case (random pivot):** Θ(n log n). Sketch
of derivation: - Let T(n) be expected time. The pivot splits
array into sizes `k` and `n-1-k` with equal probability for each
k. The expectation yields: \\[ E[T(n)] = \\frac{1}{n}
\\sum_{k=0}^{n-1} (E[T(k)] + E[T(n-1-k)]) + Θ(n). \\] This
simplifies to `E[T(n)] = (2/n) \\sum_{k=0}^{n-1} E[T(k)] + Θ(n)`.
Solving this recurrence gives `E[T(n)] = Θ(n log n)`. -
**Best-case:** perfectly balanced splits each level → T(n) =
2T(n/2) + Θ(n) → Θ(n log n). **Space:** average call stack
O(log n) for balanced recursion; O(n) worst-case. In-place (no
large aux arrays). Not stable. **Practical notes &
optimizations:** - Use randomized pivot or median-of-three to
improve pivot quality. - For arrays with many duplicate keys,
use 3-way partitioning (Dutch National Flag) to get linear time
for many duplicates. - For small subarrays (size ≤ 16), switch
to insertion sort. - Introsort: set recursion depth limit (e.g., 2 *
log n). If exceeded, switch to heapsort to guarantee O(n log
n). **Example:** partition `[4,5,3,7,2]` with pivot 2 (last) →
many elements > pivot, pivot ends up at index 0 → bad split
→ leads toward worst-case if repeated. --- ## 7. Heap Sort
**Idea.** Use a binary heap (usually max-heap) stored in the
same array. Build a max-heap, then repeatedly swap the root
(max) with the last element, reduce heap size by 1, and
heapify the root. **Pseudocode:** ``` buildMaxHeap(A): for i =
floor(n/2)-1 down to 0: heapify(A, i, n) for end = n-1 downto 1:
swap(A[0], A[end]) heapify(A, 0, end) ``` **Complexity
derivation:** - `heapify` (sift-down) cost is O(h) where h is the
height of node. - Building heap: naive upper bound O(n log
n), but exact cost is O(n) because most nodes are near leaves
and have small height. Summing heights yields O(n). - Formal
sketch: sum_{i=0}^{n-1} O(height(i)) = O(n). - Each of the n-1
extractions costs O(log n) to heapify → O(n log n). Hence
total: O(n) + O(n log n) = O(n log n). **Space:** O(1) auxiliary
(in-place). Not stable. **When to use:** When worst-case O(n
log n) with O(1) extra space is required. Slightly slower
constants than quicksort in practice. --- ## 8.
Non-comparison sorts ### 8.1 Counting Sort **Idea.** For
integer keys in `[0..k-1]`, count frequencies then write output
by iterating counts. Use prefix sums to make it stable.
**Pseudocode (stable):** ``` count[0..k-1] = {0} for each x in A:
count[x]++ for i = 1 to k-1: count[i] += count[i-1] for i = n-1
downto 0: out[count[A[i]]-1] = A[i] count[A[i]]-- return out ```
**Complexity:** O(n + k) time, O(n + k) space. Stable if
implemented with prefix sums as above. **When to use:**
When keys are integers within limited range and k is not huge
(k = O(n) or smaller), counting sort is linear. ### 8.2 Radix
Sort **Idea.** Sort keys by processing digits or groups of bits
from least significant to most significant (LSD) or vice-versa
(MSD). Use stable sort (counting sort) as the stable
subroutine. **Complexity:** Let `d` be number of digits and
`b` be base (e.g., b=10 or b=256). Time: O(d(n + b)). If `d` is
constant (e.g., 32-bit ints => d ~ 4 when using bytes), this is
O(n). Space: O(n + b). **LSD vs MSD:** - LSD: stable sort by
least significant digit upward. Works well when digit count is
fixed. - MSD: recursively bucket by most significant digit,
good for variable-length keys. **When to use:** Sorting
integers/strings when you can treat keys as sequences of
digits and `d` and `b` make overall time linear. ### 8.3 Bucket
Sort **Idea.** Distribute elements into `k` buckets (intervals),
sort each bucket (often with insertion sort), then concatenate.
**Average complexity:** If input is uniformly distributed and
`k` ≈ `n`, expected time Θ(n + k) = Θ(n). Worst-case can be
O(n^2) if all elements fall into one bucket. **Space:** O(n + k).
Stability depends on internal sort. **When to use:** When
input is uniformly distributed over a range and you can
choose bucket boundaries accordingly. --- ## 9. Hybrid &
Practical Algorithms ### 9.1 IntroSort **Idea.** Start with
quicksort for average speed; if recursion depth exceeds a
threshold (sign of degenerating splits), switch to heapsort to
guarentee O(n log n) worst-case. Also use insertion sort for
tiny partitions. **Used by:** Many std::sort implementations
(C++), because it combines practical speed with worst-case
guarantees. **Complexity:** O(n log n) worst/average, with
O(log n) stack. ### 9.2 TimSort **Idea.** Hybrid stable sorting
algorithm derived from merge sort and insertion sort used by
Python and Java's [Link] for objects. It: - Identifies
natural runs (monotonic sequences) in the data - Extends
short runs with insertion sort to at least a minimum run
length - Merges runs using a merge stack with heuristics (and
a \"galloping\" mode if one run is much larger than the other)
**Complexity:** Worst-case O(n log n), best-case O(n) when
data already has long runs. Stable. **Why practical:** Makes
use of existing order in real data (many real-world arrays
have runs), very fast in practice. --- ## 10. When to use which
sort (practical guidance) - **Small arrays (n ≤ 32):** insertion
sort or optimized insertion as base-case inside
divide-and-conquer. - **General-purpose sorting of
primitives:** quicksort (or introsort in libraries) is a common
default because of excellent practical performance. - **Need
guaranteed worst-case and O(1) extra space:** heapsort. -
**Need stability and predictable O(n log n):** merge sort. -
**Large integer keys with limited range:** counting sort or
radix sort (linear time). - **Real-world stable general-purpose
sort (objects) with adaptive behavior:** TimSort. --- ## 11.
Appendix: Recurrences & Master Theorem (short sketches)
**Master Theorem (very short):** For `T(n) = a T(n/b) + f(n)`
where `a >= 1`, `b > 1`: - If `f(n) = O(n^{c})` with `c < log_b a`
then `T(n) = Θ(n^{log_b a})`. - If `f(n) = Θ(n^{log_b a} * log^k
n)` then `T(n) = Θ(n^{log_b a} * log^{k+1} n)`. - If `f(n) =
Ω(n^{c})` with `c > log_b a` and regularity holds, then `T(n) =
Θ(f(n))`. **Examples:** - Merge sort: `T(n)=2T(n/2)+Θ(n)` →
`a=2, b=2, log_b a=1` and `f(n)=Θ(n)`, so `T(n)=Θ(n log n)`. -
Quick sort (best case): `T(n)=2T(n/2)+Θ(n)` → Θ(n log n).
Worst-case `T(n)=T(n-1)+Θ(n)` → Θ(n^2). --- ## 12. References
& further reading - *Introduction to Algorithms* — Cormen,
Leiserson, Rivest, Stein (CLRS) - *Algorithms* — Robert
Sedgewick & Kevin Wayne - Tim Peters — TimSort
description (searchable online) --- *End of document.*