Sorting Algorithms: Complete Guide with Worked Examples for GATE CS and Interviews

Sorting appears throughout GATE Algorithms and coding interviews. Memorising that quicksort is usually O(n log n) is not enough when a question asks for comparisons, intermediate passes, stability, or storage. A reliable solution combines comparison-sort mechanics, non-comparison constraints, and exact worked traces.

Sorting algorithms: comparison and non-comparison families

Quadratic sorts are bubble, selection, and insertion. Merge, quick, and heap use divide-and-conquer or heap structure to reach O(n log n) in their standard cases.

Counting sort uses an integer key range of size k; radix sort applies a stable digit pass across d positions. Their linear-looking bounds depend on k or d and do not violate the comparison-sorting lower bound. Bucket sort can also be linear on suitably distributed values, but its guarantee depends on the distribution and bucket strategy.

Bubble pushes the largest value right each pass. Selection pulls the minimum to the front. Insertion grows a sorted prefix. Merge splits and merges. Quick partitions around a pivot. Heap repeatedly extracts the maximum.

Bubble sort reaches its O(n) best case only when a swapped flag stops the algorithm after one clean pass.

Worked example 1: insertion sort, pass by pass

Sort A = [7, 3, 5, 1, 4] ascending. Count element-to-key comparisons and shifts separately.

1. i = 1, key = 3: Compare with 7, shift 7, insert 3: [3, 7, 5, 1, 4]. Comparisons: 1. Shifts: 1.

2. i = 2, key = 5: Compare with 7 then 3, shift 7: [3, 5, 7, 1, 4]. Comparisons: 2. Shifts: 1.

3. i = 3, key = 1: Compare with 7, 5, and 3, then shift all three: [1, 3, 5, 7, 4]. Comparisons: 3. Shifts: 3.

4. i = 4, key = 4: Compare with 7, 5, and 3, stopping at 3. Shift 7 and 5: [1, 3, 4, 5, 7]. Comparisons: 3. Shifts: 2.

The total is 9 comparisons and 7 element shifts. These shifts are not swaps.

On a nearly sorted array, insertion sort makes about n comparisons and few shifts, so it suits almost sorted data. Selection still makes n(n-1)/2 comparisons whatever the order, or 5×4/2 = 10 here.

Worked example 2: one quicksort partition, done honestly

Use Lomuto partition with the last element as pivot on A = [4, 9, 3, 7, 1, 6]. Pivot 6 has i starting before the array while j scans indices 0 through 4.

1. j = 0: 4 < 6, so i = 0. Self-swap: [4, 9, 3, 7, 1, 6].

2. j = 1: 9 is not less than 6. No move.

3. j = 2: 3 < 6, so i = 1. Swap 9 and 3: [4, 3, 9, 7, 1, 6].

4. j = 3: 7 is not less than 6. No move.

5. j = 4: 1 < 6, so i = 2. Swap 9 and 1: [4, 3, 1, 7, 9, 6].

6. Final: Swap A[3] with the pivot: [4, 3, 1, 6, 9, 7]. Pivot 6 is fixed at index 3.

This partition makes 5 comparisons. Its left subarray is [4, 3, 1], and its right subarray is [9, 7]. Every non-pivot element is compared with the pivot once, so partitioning n elements costs n-1 comparisons.

For an array-after-partition question, name Lomuto or Hoare because the intermediate arrangement depends on the scheme.

Why merge and heap sort never degrade

Merge sort follows T(n) = 2T(n/2) + cn. For n = 8, unrolling gives 2T(4) + 8c, then 4T(2) + 16c, then 8T(1) + 24c. Three merge levels touch all eight elements, so the work is 8×3 = 24 c-units, matching n log2 n. Merging two sorted runs of length four needs at most seven comparisons, or n-1 for eight elements.

Merge sort pays O(n) extra array space. It is the standard stable O(n log n) choice.

Heap sort builds a heap in O(n), not O(n log n), because nodes near the leaves need little or no downward movement. Then n extract-max operations at O(log n) each give O(n log n) in every case with O(1) extra space.

Quicksort averages O(n log n) with small constants, but it can degrade. On already sorted input, choosing the last element as pivot produces partitions of sizes 0 and n-1, leading to O(n^2).

Stability and in-place: two words that decide MSQ marks

A stable sort preserves equal-key order. Sorting [(2, a), (1, b), (2, c)] by number must leave (2, a) before (2, c). Bubble, insertion, and merge are stable. Standard selection, quick, and heap are not.

For multi-key sorting, sort records by name first and then stably by marks. Names remain ordered among equal marks. Radix sort also needs a stable digit sort.

In exam tables, in-place means constant auxiliary storage, with quicksort still classed as in-place despite its average O(log n) recursion stack. Standard merge sort needs O(n) extra space.

The classic false statement is that selection sort is stable. Its long-distance swap can jump one equal element over another.

How GATE and interviews actually test sorting

The official GATE CS syllabus lists searching, sorting, and hashing within Programming and Data Structures. Sorting questions commonly use five patterns:

1. Array after k passes: Trace bubble, insertion, or selection as above.

2. NAT counts: Count comparisons, swaps, or shifts. Here insertion used 9 comparisons and a partition used n-1.

3. Recurrences: Solve expressions such as T(n) = 2T(n/2) + n.

4. MSQ properties: Select algorithms that are stable, in-place, or worst-case O(n log n).

5. Input scenarios: Choose insertion for nearly sorted arrays, merge for linked lists, and heap for guaranteed O(n log n) time with O(1) extra space.

Data Structures and Algorithms form a substantial part of CS preparation, with sorting repeatedly tested. Practise through Data Structures MCQs, then use the GATE Test Series, Mocks & Topic-wise Tests for mocks.

Interviews may ask you to write a partition, explain why quicksort suits arrays, or reject it when stability is required or adversarial or sorted input can meet a poor pivot rule without randomisation.

Traps that cost real marks

• Calling bubble sort O(n^2) in the best case: That is true without early exit. With a swapped flag, one clean pass over sorted data gives O(n). State the assumed version.

• Confusing shifts with swaps: The insertion trace has 7 shifts, not 7 swaps. A NAT answer can change with that word.

• Using the average quicksort recurrence everywhere: Last-element pivot on sorted input creates the worst case, not the best.

• Calling heap or quicksort stable: Neither is stable in its standard form.

• Forgetting merge space: O(n log n) time does not remove its O(n) auxiliary array cost.

The short version, and where to go next

Use the table to choose a family, then practise one quadratic trace and one named partition. Explain merge and heap bounds from their invariants, and test every stability claim with equal-key records.

For structured coverage of the complete Algorithms syllabus, use Zero to Hero, Complete CS Course and the GATE CS Exam Preparation hub.