Sorting algorithms

In short

Sorting arranges records in non-decreasing (or non-increasing) order of a key, and it is the most-examined single topic in data structures and algorithms because almost every other technique — binary search, grouping, deduplication, two-pointer and sliding-window solutions, database joins — assumes sorted input. A standard syllabus covers the three elementary O(n²) sorts, the three O(n log n) comparison sorts, the Ω(n log n) comparison lower bound, and the linear-time counting/radix/bucket sorts that beat it by not comparing keys. GATE CS asks it almost every year (trace a pass, count comparisons or swaps, identify stability, recognise a worst case), and placement rounds at TCS NQT, Infosys, Wipro, Cognizant, Zoho, Amazon India, Flipkart, Paytm and Zerodha ask it in both written and whiteboard form. In production you rarely write a sort — you choose one, and you must justify the choice on stability, memory, data distribution and worst-case guarantee.

Explained

Definitions and classification

• Key, record, satellite data: the key is sorted on; the rest of the record moves with it. Sorting large records usually sorts an array of pointers/indices instead of moving records.
• Comparison sort: decides only by comparing pairs (a ≤ b). Bubble, selection, insertion, shell, merge, quick, heap.
• Non-comparison (distribution) sort: uses the key's *value* as an address — counting, radix, bucket. Only possible when keys are integers or digit strings in a bounded range.
• In-place: uses O(1) or O(log n) auxiliary space beyond the input array. Insertion, selection, bubble, heap and (by convention) quicksort are in-place; classical merge sort is not.
• Stable: equal keys keep their original relative order. Insertion, bubble, merge, counting, radix (with a stable digit pass) are stable; selection, shell, quick and heap are not.
• Adaptive: runs faster on partly sorted data — insertion sort, bubble sort with a swap flag, Timsort. Selection and heap sort are non-adaptive.
• Internal vs external: internal sorting assumes the data fits in RAM; external sorting handles files larger than RAM (disk/tape passes).
• Online: can accept elements one at a time — insertion sort is online; merge and quick sort are not.
• Inversion: a pair (i, j) with i < j but a[i] > a[j]. A sorted array has 0 inversions; a reverse-sorted array has n(n−1)/2. Inversions measure "how unsorted" an array is and exactly equal the shift count of insertion sort.

Elementary O(n²) sorts

• Bubble sort: repeatedly sweep the array, swapping adjacent out-of-order pairs; after pass i the largest i elements are in place. Comparisons n(n−1)/2; swaps = number of inversions. With a swapped flag it terminates in one pass (n−1 comparisons) on sorted data, so best case Θ(n).
• Selection sort: in pass i, scan the unsorted suffix for its minimum and swap it into position i. Always n(n−1)/2 comparisons and at most n−1 swaps — the fewest writes of any simple sort, which matters for flash memory or costly record moves. Not stable (the long-range swap jumps over equal keys).
• Insertion sort: take a[i] as *key*, shift larger elements of the sorted prefix one place right, drop the key into the hole. Best case Θ(n) (already sorted), worst Θ(n²) (reverse sorted), average Θ(n²). For a nearly sorted array with d inversions it runs in Θ(n + d). Stable, in-place, online, and the fastest of all sorts for small n (~10–40 elements) because of tiny constants — which is why library sorts cut over to it for small sub-arrays.
• Binary insertion sort: find the position by binary search (Θ(n log n) comparisons) but shifting is still Θ(n²) moves, so the overall time stays Θ(n²).
• Shell sort: insertion sort on sub-arrays of elements that are *gap* apart, with the gap decreasing to 1. Early passes move elements long distances, killing many inversions cheaply. Complexity depends on the gap sequence: Θ(n²) for Shell's n/2 halving, Θ(n^1.5) for Knuth's (3^k−1)/2 = 1, 4, 13, 40, 121…, about Θ(n^1.25) empirically for Sedgewick's. In-place, not stable, no extra memory — used in embedded code.

The O(n log n) comparison sorts

• Merge sort: split the array in half, sort each half recursively, then merge the two sorted halves in linear time with two indices. Guaranteed Θ(n log n) in all cases; stable; needs Θ(n) auxiliary space (recursion depth ⌈log₂ n⌉).
  • *Bottom-up (iterative) merge sort* merges runs of width 1, 2, 4, … and avoids recursion.
  • Linked lists: merge sort is the sort of choice — merging needs only pointer re-linking, so extra space is O(1) (plus O(log n) stack) and no random access is required.
  • It is also the basis of external sorting and of counting inversions.
• Quicksort: choose a pivot, partition the array so that all keys ≤ pivot lie left and all > pivot lie right, then recurse on the two parts. No merge step — the work is done before recursing.
  • Lomuto partition: one forward index i marking the end of the "≤ pivot" zone; n−1 comparisons, simple, but does many swaps and degrades badly on arrays of equal keys.
  • Hoare partition: two indices moving inwards and swapping; fewer swaps, handles duplicates better; the pivot does not end up in its final place.
  • Three-way (Dutch national flag) partition: splits into < , = , > and is Θ(n) on arrays with few distinct keys.
  • Worst case Θ(n²) — occurs when the pivot is always the extreme element, e.g. last-element pivot on already sorted or reverse-sorted input, giving recursion depth n. Average case Θ(n log n) with a small constant.
  • Fixes: randomised pivot, median-of-three (first, middle, last), median-of-medians (worst-case linear pivot, large constants), recurse on the smaller side and loop on the larger (tail-call elimination) to bound stack at O(log n), and switch to insertion sort below a cut-off of ~10–16.
  • Not stable. Fastest general-purpose in-memory sort in practice because of cache locality and in-place operation.
• Heap sort: build a max-heap in the array (bottom-up heapify, Θ(n)), then repeatedly swap a[0] with the last active element, shrink the heap and sift down — n−1 extractions of Θ(log n) each.
  • Θ(n log n) in best, average and worst case; in-place, O(1) extra space; not stable; non-adaptive. Slower than quicksort in practice (poor cache locality, ~2× comparisons) but has no bad input, so it is the safety net inside introsort.
  • 0-based index relations: parent = ⌊(i−1)/2⌋, children 2i+1 and 2i+2; 1-based: parent ⌊i/2⌋, children 2i, 2i+1. A heap of n nodes has ⌈n/2⌉ leaves, and heapify starts at index ⌊n/2⌋−1 (0-based).
• Hybrid library sorts: introsort (C++ std::sort) = quicksort + switch to heap sort when depth exceeds ~2log₂n + insertion sort for small ranges — average quicksort speed with an O(n log n) guarantee. Timsort (Python sorted/list.sort, Java Arrays.sort for objects) detects natural ascending/descending runs, extends short runs to a minrun of 32–64 with binary insertion sort, and merges runs under a stack invariant with galloping; it is stable and Θ(n) on already sorted data (recent CPython releases refine the merge rule — the "powersort" policy). Java uses dual-pivot quicksort for primitive arrays (stability is meaningless there) and Timsort for object arrays (stability is guaranteed by the API). C's qsort takes a comparison function pointer and is typically a quicksort variant, unspecified as to stability.

Linear-time sorts: counting, radix, bucket

• Counting sort: for integer keys in 0…k, count occurrences in C[], take the prefix sum so C[v] = number of keys ≤ v, then place each element from right to left into its output slot, decrementing C[v]. Θ(n + k) time, Θ(n + k) space, stable. Right-to-left traversal is what makes it stable; negative or shifted ranges need an offset. Useless when k ≫ n (e.g. 32-bit keys).
• Radix sort (LSD): apply a stable counting sort on each digit from least significant to most, d passes for d digits in base b. Θ(d(n + b)); for fixed-width keys this is Θ(n). The inner sort *must* be stable, otherwise earlier (lower-order) digit work is destroyed. MSD radix sort recurses from the most significant digit and suits strings of unequal length.
• Bucket sort: for keys uniformly distributed over [0, 1), scatter into n buckets by ⌊n·key⌋, insertion-sort each bucket, concatenate. Θ(n) average under the uniformity assumption, Θ(n²) worst case (all keys in one bucket).
• These beat n log n only because they never compare two keys — they assume structure in the key, so they are not counter-examples to the lower bound.

The Ω(n log n) lower bound and special cases

• Decision-tree argument: any comparison sort on n distinct elements is a binary tree whose internal nodes are comparisons and whose leaves are the possible outputs. All n! permutations must appear as leaves, and a binary tree of height h has at most 2^h leaves, so 2^h ≥ n! → h ≥ log₂(n!).
• By Stirling, log₂(n!) = n log₂ n − n log₂ e + O(log n) ≈ n log₂ n − 1.4427n, hence worst-case comparisons = Ω(n log n). Merge sort and heap sort are therefore asymptotically optimal.
• The same bound applies to the *average* number of comparisons (average leaf depth ≥ log₂(n!)).
• Exact minima for tiny n (information-theoretic bound ⌈log₂ n!⌉ and known optimum): n = 4 → 5; n = 5 → 7; n = 8 → ⌈15.30⌉ = 16; merge-insertion (Ford–Johnson) achieves these small optima.
• Parallel/network sorting: sorting networks such as bitonic sort sort in O(log²n) parallel steps with O(n log²n) comparators — asked in advanced/parallel-algorithm papers.

External sorting and choosing an algorithm

• External merge sort: (1) read chunks that fit in memory, sort each internally (quicksort/heap sort) and write them out as runs; (2) merge runs m-way using one input buffer per run and one output buffer, repeating until one run remains. Replacement selection with a heap produces initial runs averaging 2M in length.
• Cost is dominated by disk I/O, so the measure is number of passes, not comparisons; a higher merge order m means fewer passes.
• Decision checklist: need stability → merge/Timsort or counting/radix. Memory-tight embedded code → heap or shell sort. Small n or nearly sorted → insertion sort. Linked list → merge sort. Bounded small integer keys → counting/radix. Hard real-time worst case → heap or merge sort, never plain quicksort. General in-memory speed → quicksort/introsort.
• Related use of the same machinery: partition alone gives quickselect for the k-th smallest (average Θ(n)), and a heap gives top-k in Θ(n log k).

Key points

• Stable sort – equal keys keep input order; required when sorting by a second field after a first (e.g. sort by marks, then by roll number).
• In-place – O(1)/O(log n) extra space; merge sort is *not* in-place, quick/heap/insertion are.
• Bubble sort – adjacent swaps; swaps = inversions; Θ(n) best case only with the swap flag.
• Selection sort – exactly n(n−1)/2 comparisons and ≤ n−1 swaps; minimum data movement; unstable.
• Insertion sort – Θ(n + inversions); best for small or nearly sorted arrays; stable, online.
• Shell sort – gap-based insertion sort; Θ(n^1.5) with Knuth gaps; in-place, unstable.
• Merge sort – Θ(n log n) always, stable, Θ(n) extra space, best for linked lists and external data.
• Quicksort – average Θ(n log n), worst Θ(n²) on sorted input with a bad pivot; in-place, unstable, fastest in practice.
• Partition – the whole of quicksort's work; Lomuto (one index), Hoare (two indices), 3-way for duplicates.
• Heap sort – Θ(n log n) in every case, O(1) space, unstable; build-heap is Θ(n), not Θ(n log n).
• Counting sort – Θ(n + k), stable, needs bounded integer keys; prefix sums give final positions.
• Radix sort – d stable digit passes, Θ(d(n + b)); the inner sort must be stable.
• Bucket sort – Θ(n) average under uniform distribution, Θ(n²) worst.
• Lower bound – any comparison sort needs ≥ ⌈log₂(n!)⌉ ≈ n log₂ n − 1.44n comparisons.
• Introsort – quicksort + heap-sort fallback + insertion sort; C++ std::sort.
• Timsort – run detection + stable merging; Python sorted, Java object arrays; Θ(n) on sorted input.
• Inversions – count of out-of-order pairs; 0 when sorted, n(n−1)/2 when reversed; counted in Θ(n log n) by merge sort.
• External sort – measured in disk passes: sort runs, then m-way merge.

Formulas and examples

Example 1 — Insertion sort trace, comparisons and inversions on [5, 2, 4, 6, 1, 3]

• Total comparisons = 12, shifts = 9.
• Inversions: (5,2)(5,4)(5,1)(5,3)(2,1)(4,1)(4,3)(6,1)(6,3) = 9 — equal to the shift count, as the formula requires. Comparisons = 9 inversions + 3 early stops (i = 2, 3, 5) = 12. ✓

Example 2 — Merge sort comparisons for n = 8, against the lower bound

• T(1) = 0; T(2) = 2(0) + 1 = 1; T(4) = 2(1) + 3 = 5; T(8) = 2(5) + 7 = 17.
• Closed form: n log₂n − n + 1 = 8(3) − 8 + 1 = 17. The naive n log₂n estimate is 24.
• Lower bound: 8! = 40,320; log₂40,320 ≈ 15.30 → at least 16 comparisons are needed. Merge sort uses 17 — within 1 of optimal, confirming it is asymptotically optimal but not exactly optimal.

Example 3 — Lomuto partition on [8, 3, 5, 1, 9, 4, 7], pivot = last = 7

i = -1, pivot = 7 (index 6)
j=0: 8 > 7            -> 8 3 5 1 9 4 7
j=1: 3 <= 7, i=0, swap-> 3 8 5 1 9 4 7
j=2: 5 <= 7, i=1, swap-> 3 5 8 1 9 4 7
j=3: 1 <= 7, i=2, swap-> 3 5 1 8 9 4 7
j=4: 9 > 7            -> 3 5 1 8 9 4 7
j=5: 4 <= 7, i=3, swap-> 3 5 1 4 9 8 7
swap a[i+1]=a[4] with a[6] -> 3 5 1 4 | 7 | 8 9

• 6 comparisons (n−1), pivot lands at index 4, sub-problems of size 4 and 2. If the input had been 1 3 4 5 7 8 9 with the same last-element pivot rule, every partition would split 6+0, 5+0, … giving 6+5+4+3+2+1 = 21 = n(n−1)/2 comparisons — the Θ(n²) worst case.

Example 4 — Counting sort on A = [2, 5, 3, 0, 2, 3, 0, 3], k = 5

• Counts C: C[0]=2, C[1]=0, C[2]=2, C[3]=3, C[4]=0, C[5]=1 (total 8 ✓).
• Prefix sums: C = [2, 2, 4, 7, 7, 8] — "number of keys ≤ v".
• Scanning A right to left, each key v goes to output index C[v]−1, then C[v]−−. Final output: [0, 0, 2, 2, 3, 3, 3, 5], with the three 3s in their original relative order (stable).
• Cost = Θ(n + k) = 8 + 6 operations-order, versus 8 log₂8 = 24 comparisons for a comparison sort.

Example 5 — Radix sort: choosing the base for 1,00,000 keys < 10⁶

• Base b = 10: d = 6 passes → work ≈ d(n + b) = 6(1,00,000 + 10) = 6,00,060.
• Base b = 1,000: d = ⌈log₁₀₀₀ 10⁶⌉ = 2 passes → 2(1,00,000 + 1,000) = 2,02,000, about 3× less, at the cost of a 1,000-entry count array.
• A comparison sort would need ≈ n log₂n = 1,00,000 × 16.6 ≈ 16.6 lakh comparisons.

Example 6 — External sort of a 100 GB file with 4 GB usable memory, 16-way merge

• Initial runs: 100/4 = 25 runs of 4 GB (pass 1).
• Merge passes = ⌈log₁₆ 25⌉ = ⌈1.16⌉ = 2. Total passes = 1 + 2 = 3, i.e. about 300 GB read + 300 GB written.

*Heap sort is Θ(n) only in the degenerate case of all-equal keys.

Where it is used

• Databases and analytics: ORDER BY, GROUP BY, sort-merge joins and index builds in MySQL, PostgreSQL and Oracle use external merge sort with a configurable sort buffer; EXPLAIN showing "Using filesort" is exactly this.
• Banking and payments batch jobs: NPCI/UPI and NACH settlement files, end-of-day reconciliation at HDFC/ICICI/SBI and clearing files are sorted by account or reference key before matching — classic external sorting on fixed-width keys (radix/counting friendly).
• Order books and ticketing: Zerodha/NSE-BSE order matching keeps price-time priority (a stable ordering on timestamp after price); IRCTC and BookMyShow sort availability and seat lists per request.
• Search, recommendation and e-commerce: Flipkart/Amazon India "sort by price / rating / relevance" is a top-k heap or partial sort over millions of SKUs rather than a full sort.
• Big-data stacks: the shuffle-and-sort stage of MapReduce/Hadoop, Spark's sort-based shuffle and Timsort-backed sortBy, and Aadhaar/UIDAI-scale deduplication pipelines, which sort to bring duplicate keys adjacent.
• Job roles and exams: SDE and backend interviews (whiteboard partition/merge code), embedded firmware (shell/insertion sort in a few hundred bytes of RAM), and written tests — GATE CS/DA, ISRO, BARC, DRDO, UGC-NET and PSU recruitment.

Interview questions

• Q: Why is quicksort usually faster than merge sort despite the same average complexity? A: It sorts in place with sequential, cache-friendly access and no copying back from an auxiliary array, so its constant factor is smaller; merge sort pays Θ(n) extra memory traffic per level.
• Q: What is a stable sort and when does stability actually matter? A: A stable sort preserves the input order of equal keys; it matters when sorting on multiple fields in sequence (sort by roll number, then stably by marks) and in radix sort, whose correctness depends on it.
• Q: Which sort would you use for a linked list and why? A: Merge sort — it needs no random access, merges by re-linking pointers in O(1) extra space, and stays Θ(n log n); quicksort on a list loses its locality advantage.
• Q: When is quicksort O(n²) and how do you prevent it? A: When the pivot is repeatedly the smallest or largest element, e.g. a last-element pivot on sorted or reverse-sorted data; prevent it with a randomised or median-of-three pivot, 3-way partitioning for duplicates, and a heap-sort fallback (introsort).
• Q: Can any sort beat n log n? A: No comparison sort can, by the decision-tree bound h ≥ log₂(n!); counting, radix and bucket sort achieve linear time only by exploiting key values instead of comparisons.
• Q: Heap sort has an O(n log n) worst case and O(1) space — why isn't it the default library sort? A: Its sift-down jumps around memory, giving poor cache behaviour and roughly twice quicksort's comparisons, so it is used as a guard inside introsort rather than as the main algorithm.
• Q: You must sort 10 crore 32-bit integers. Counting sort? A: Not directly — k = 2³² makes the count array far too large; use LSD radix sort with base 2¹⁶ (two passes) or an introsort/parallel sort.
• Q: Is merge sort in-place? A: No — the standard merge needs Θ(n) auxiliary space; in-place merge variants exist but are either Θ(n log²n) or have large constants, and the linked-list version is in-place only because merging re-links nodes.
• Q: What is the minimum number of comparisons needed to sort 5 elements? A: Seven — the information bound is ⌈log₂ 120⌉ = ⌈6.91⌉ = 7, and Ford–Johnson merge insertion attains it.
• Q: Data arrives almost sorted (a few late entries). Best choice? A: Insertion sort or Timsort — insertion sort runs in Θ(n + inversions) and Timsort detects existing runs, both approaching Θ(n); quicksort gets no benefit and may hit its worst case.
• Q: Difference between the comparisons and the swaps of selection sort? A: Comparisons are always n(n−1)/2 regardless of input, but swaps are at most n−1 — which is why it is chosen when writes are expensive, e.g. flash/EEPROM.
• Q: How do you count inversions in an array efficiently? A: Modify merge sort: when an element from the right half is taken before the remaining k elements of the left half, add k — total Θ(n log n), against Θ(n²) for the brute-force pair check.

Common mistakes

• Claiming bubble sort is Θ(n) on sorted input without mentioning the swapped-flag early exit; the plain double loop is Θ(n²) on every input.
• Calling quicksort O(n log n) in the worst case, or calling it stable — it is neither.
• Saying merge sort is in-place, or forgetting its Θ(n) auxiliary array when asked about space complexity.
• Stating build-heap as Θ(n log n); the bottom-up heapify is Θ(n), and only the n extractions make heap sort Θ(n log n).
• Using an unstable inner sort in LSD radix sort, or applying counting sort to floats, negatives (without an offset) or a huge key range.
• Off-by-one errors in partition code: wrong initial i = low−1, looping j up to high instead of high−1, or an index crossing that loops forever in Hoare partition when many keys equal the pivot.
• Quoting average-case behaviour where the question asks for the worst case (and vice versa), and mixing up comparisons with swaps/shifts when a GATE question asks for an exact count.

Related topics

Time and space complexity · Divide and conquer · Searching and binary search · Heaps and priority queues · DSA interview patterns · Hashing and database indexing