Sorting is the single most examined algorithmic topic in GATE, and it is where careless aspirants leak marks. The trap is treating six algorithms as six unrelated recipes. They are not. Once you compare them on the same axes, best case, average case, worst case, stability, and memory, the whole topic collapses into one table you can reconstruct from first principles.
Sorting algorithms: what you are actually comparing
Every sorting question is asking about one of five properties. Fix these axes and you can classify any algorithm.
Time complexity in the best, average, and worst case, as a function of the number of elements n.
Stability. A sort is stable if two equal keys keep their original relative order. This matters when you sort records by a secondary key.
In-place. An in-place sort uses only O(1) extra memory beyond the input array.
Comparison versus non-comparison. A comparison sort decides order only by comparing pairs of keys. A non-comparison sort exploits the structure of the keys themselves.
Adaptivity. An adaptive sort runs faster on input that is already nearly sorted.
The elementary sorts: bubble, insertion, selection
These three run in O(n²) on average and are the examiner's warm-up.
Bubble sort repeatedly swaps adjacent out-of-order pairs, letting the largest element "bubble" to the end each pass. With an early-exit flag it detects an already-sorted array in one pass, giving a best case of O(n). It is stable and in-place.
Insertion sort grows a sorted prefix, inserting each new element into its correct place. On nearly-sorted data it is O(n), which makes it the fastest choice for small or almost-ordered arrays. Stable and in-place.
Selection sort repeatedly selects the minimum of the unsorted suffix and swaps it into place. It always does the same work, so best, average, and worst are all O(n²). It is not stable, because a long-distance swap can jump one equal key past another.
Merge sort and quicksort: divide and conquer
Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves. The merge is the heart of it. Suppose we merge two sorted runs, [2, 5, 8] and [1, 3, 9].
Compare fronts 2 and 1, take 1. Result: [1].
Compare 2 and 3, take 2. Result: [1, 2].
Compare 5 and 3, take 3. Result: [1, 2, 3].
Compare 5 and 9, take 5. Result: [1, 2, 3, 5].
Compare 8 and 9, take 8, then append the leftover 9. Result: [1, 2, 3, 5, 8, 9].
Merging two runs of total length n is O(n), and there are log n levels of splitting, so merge sort is Θ(n log n) in all cases. It is stable but needs O(n) extra memory, so it is not in-place.
Quicksort picks a pivot, partitions the array so smaller elements go left and larger go right, then recurses. Here is a Lomuto partition of A = [7, 2, 1, 8, 6, 3, 5, 4] with pivot 4 (the last element). We keep a boundary index i for the "less than or equal to pivot" region.
j = 0: A[0] = 7 > 4, skip.
j = 1: A[1] = 2 ≤ 4, advance i to 0, swap into place. Array: [2, 7, 1, 8, 6, 3, 5, 4].
j = 2: A[2] = 1 ≤ 4, advance i to 1, swap. Array: [2, 1, 7, 8, 6, 3, 5, 4].
j = 3, 4: 8 and 6 both exceed 4, skip.
j = 5: A[5] = 3 ≤ 4, advance i to 2, swap. Array: [2, 1, 3, 8, 6, 7, 5, 4].
j = 6: A[6] = 5 > 4, skip.
Finally swap the pivot into position i + 1 = 3, giving [2, 1, 3, 4, 6, 7, 5, 8]. The pivot 4 is now in its final sorted slot with everything smaller to its left. Quicksort then recurses on the two sides.
[DIAGRAM: The Lomuto partition as a bar chart of the eight values, with the boundary index i and scanner j marked, the pivot 4 highlighted, and an arrow showing the final swap that lands the pivot at index 3.]
Quicksort is O(n log n) on average when partitions are balanced, but O(n²) in the worst case, when the pivot is always the smallest or largest element (a sorted array with a fixed end pivot). It is in-place but not stable.
Heap sort
Heap sort builds a max-heap, then repeatedly extracts the maximum to the end of the array. Building the heap is O(n) and each of the n extractions costs O(log n), so it is Θ(n log n) in every case, in-place, but not stable. It is the algorithm that gives you guaranteed n log n without merge sort's extra memory.
The Ω(n log n) comparison lower bound
Why can no comparison sort beat n log n? Model any comparison sort as a binary decision tree, where each internal node is one comparison and each leaf is one possible ordering of the input. For n distinct elements there are n! possible orderings, so the tree needs at least n! leaves. A binary tree with n! leaves has height at least log₂(n!), and by Stirling's approximation log₂(n!) is Θ(n log n). The height equals the worst-case number of comparisons, so every comparison sort is Ω(n log n). This is a proof, not a heuristic, and examiners ask it directly.
[DIAGRAM: A decision tree for sorting three elements a, b, c. The root compares a and b, each child compares another pair, and the six leaves list the six permutations, illustrating that log base 2 of 3 factorial comparisons are needed.]
Non-comparison sorts: counting and radix
If keys are integers in a small range, you can beat the bound because you are no longer only comparing. Counting sort counts occurrences of each key value and reconstructs the array in O(n + k) time, where k is the range of key values. It is stable. Radix sort applies a stable sort (usually counting sort) digit by digit, from least significant to most significant, running in O(d(n + k)) for d-digit keys. These are linear only when k and d are small relative to n, which is exactly the constraint examiners test.
Sorting complexity: the comparison table
Algorithm | Best | Average | Worst | Stable | In-place |
|---|---|---|---|---|---|
Bubble | O(n) | O(n²) | O(n²) | Yes | Yes |
Insertion | O(n) | O(n²) | O(n²) | Yes | Yes |
Selection | O(n²) | O(n²) | O(n²) | No | Yes |
Merge | O(n log n) | O(n log n) | O(n log n) | Yes | No |
Quick | O(n log n) | O(n log n) | O(n²) | No | Yes |
Heap | O(n log n) | O(n log n) | O(n log n) | No | Yes |
How sorting is tested in GATE, NET and placements
GATE CS favours the corner cases: the worst-case input for quicksort, the exact count of comparisons or swaps for a small array, which sorts are stable, and the decision-tree lower-bound argument. A recurring numerical asks you to hand-trace one partition or one merge, so the worked examples above are the exact drill. To place sorting inside the wider algorithms syllabus, the Algorithms learn module sequences it with searching and complexity analysis.
UGC NET Computer Science leans conceptual: match an algorithm to its complexity, identify stability, and distinguish comparison from non-comparison sorts. Placement tests ask you to code quicksort or merge sort and reason about when each is preferable, and often connect sorting to later topics like the graph algorithms behind BFS, DFS and shortest paths or the optimisation patterns in dynamic programming.
The short version
Learn the comparison table by understanding, not memory: the O(n²) sorts trade simplicity for speed, merge and heap sort guarantee n log n, quicksort is fast on average but quadratic on a bad pivot, and non-comparison sorts win only when the key range is small. Hand-trace one partition and one merge, then prove the n log n lower bound once. For GATE-depth practice across the whole algorithms syllabus, GATE Guidance by Sanchit Sir sequences these with hundreds of solved questions, and the GATE CS exam category collects the rest of the paper. Do the tracing by hand and sorting becomes guaranteed marks.