By Piyush Wairale · GATE DA Educator & Course Instructor, IIT Madras BS Programme · Updated August 2026

Bubble Sort, Traced Pass by Pass

Bubble sort repeatedly walks the array, swapping adjacent out-of-order pairs; after pass k the k largest elements are locked at the end. Trace on [5, 2, 9, 1, 7, 3]:

Pass 1: 5↔2 → [2,5,9,1,7,3]; 5,9 ok; 9↔1 → [2,5,1,9,7,3]; 9↔7 → [2,5,1,7,9,3]; 9↔3 → [2,5,1,7,3,9] — 4 swaps, 9 settled.

Pass 2: 2,5 ok; 5↔1 → [2,1,5,7,3,9]; 5,7 ok; 7↔3 → [2,1,5,3,7,9] — 2 swaps, 7 settled.

Pass 3: 2↔1 → [1,2,5,3,7,9]; 5↔3 → [1,2,3,5,7,9] — 2 swaps. Pass 4: no swaps → early exit. Total: 8 swaps, 4 passes. The swap count equals the number of inversions in the original array — a fact GATE has turned into a NAT more than once. This post is the deep-dive companion to the Python & DSA pillar guide.

Insertion and Selection Sort on the Same Array

Insertion sort grows a sorted prefix, inserting each new key into place (like sorting cards in hand). On [5, 2, 9, 1, 7, 3]:

key 2 → [2, 5, 9, 1, 7, 3]; key 9 stays → [2, 5, 9, 1, 7, 3]; key 1 shifts three → [1, 2, 5, 9, 7, 3]; key 7 → [1, 2, 5, 7, 9, 3]; key 3 → [1, 2, 3, 5, 7, 9]. Best case (already sorted) is O(n) — the only quadratic-family algorithm with a linear best case, and a favourite MCQ.

Selection sort finds the minimum of the unsorted suffix and swaps it to the front: [1, 2, 9, 5, 7, 3] → [1, 2, 9, 5, 7, 3] → [1, 2, 3, 5, 7, 9] → done after checks. It always makes exactly n(n−1)/2 comparisons — best, worst and average — but at most n−1 swaps, the fewest of any comparison sort here. “Minimum swaps to sort” questions usually want selection-sort reasoning.

Merge Sort: Recursion Tree and the Merge Step

The merge step, element by element. Merging sorted halves [2, 5, 9] and [1, 3, 7] with two pointers: compare 2 vs 1 → take 1; 2 vs 3 → take 2; 5 vs 3 → take 3; 5 vs 7 → take 5; 9 vs 7 → take 7; left copy the tail → 9. Result [1, 2, 3, 5, 7, 9] in 5 comparisons. Merging two runs of sizes m and n costs at most m + n − 1 comparisons; log₂n levels of merging, each touching all n elements, gives the famous Θ(n log n) in every case — merge sort has no bad inputs, at the price of O(n) auxiliary space.

Quicksort: the Lomuto Partition, Traced

Lomuto partition on [5, 2, 9, 1, 7, 3] with pivot = last element = 3. Pointer i marks the end of the “≤ pivot” zone (starts at −1); j scans left to right:

j=0: 5 > 3, skip.  j=1: 2 ≤ 3 → i=0, swap a[0]↔a[1] → [2, 5, 9, 1, 7, 3].  j=2: 9 > 3, skip.  j=3: 1 ≤ 3 → i=1, swap a[1]↔a[3] → [2, 1, 9, 5, 7, 3].  j=4: 7 > 3, skip.

Final step: swap a[i+1] = a[2] with the pivot → [2, 1, 3, 5, 7, 9]. Pivot 3 is now at index 2 — its final sorted position, with everything smaller on its left and larger on its right (each side not yet sorted internally). That invariant is how you recognise a quicksort snapshot in “which algorithm produced this state?” MCQs. Recursion then handles [2, 1] and [5, 7, 9]. Worst case: already-sorted input with last-element pivots gives n−1 lopsided partitions → O(n²); random pivots make that vanishingly unlikely.

Binary Search, Traced with a lo/mid/hi Table

Search for 9 in [1, 2, 3, 5, 7, 9] (indices 0–5):

Worst case on n elements: ⌈log₂(n+1)⌉ comparisons (n = 1000 → 10). It requires a sorted array — pair it mentally with sorting cost when a question asks “sort once, then search k times”.

The Complexity Table GATE Tests Every Year

The Python Implementations to Know

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:          # early exit: sorted
            break
    return a

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= keeps it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

def quicksort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo < hi:
        p = a[hi]; i = lo - 1          # Lomuto partition
        for j in range(lo, hi):
            if a[j] <= p:
                i += 1; a[i], a[j] = a[j], a[i]
        a[i+1], a[hi] = a[hi], a[i+1]
        quicksort(a, lo, i); quicksort(a, i + 2, hi)
    return a

def binary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x: return mid
        if a[mid] < x: lo = mid + 1
        else: hi = mid - 1
    return -1

Three GATE-Style Problems, Solved

Problem 1 (NAT). How many swaps does bubble sort make on [4, 3, 2, 1]?

Solution. Swaps = inversions. Every pair is inverted: C(4,2) = 6. (Trace check: pass 1 → 3 swaps, pass 2 → 2, pass 3 → 1.)

Problem 2 (MCQ). Sorting [5, 2, 9, 1, 7, 3] ascending, an algorithm’s state after some steps is [2, 1, 3, 5, 7, 9] where 3 was the last element originally. Which algorithm?

Solution. The original last element sits at its final position with smaller-unsorted values left and larger values right — the Lomuto partition signature → quicksort (it’s exactly our traced partition). Insertion would show a sorted prefix with the suffix untouched in original order; selection would have 1 and 2 in place first.

Problem 3 (NAT). Maximum comparisons for binary search on a sorted array of 63 elements?

Solution. ⌈log₂(63+1)⌉ = log₂64 = 6. Each comparison halves the candidates: 63 → 31 → 15 → 7 → 3 → 1 → found.

Common Mistakes to Avoid

Confusing pass counts with swap counts. Bubble sort’s swaps = inversions; its passes = 1 + (largest displacement toward the front).

Marking selection sort stable. The long-range swap can jump one equal element over another — canonical counterexample: [2a, 2b, 1].

Saying quicksort is always O(n log n). Worst case is O(n²) — sorted input with last-element pivot. Merge sort is the one with a guaranteed n log n.

Forgetting merge sort’s O(n) extra space when a question asks for an in-place O(n log n)-average sort (answer: quicksort).

Off-by-one in binary search traces. mid = (lo + hi) // 2 floors; recompute it every iteration and update lo = mid + 1 / hi = mid − 1, never lo = mid.

How GATE DA Asks Sorting

The programming section mixes Python reading with algorithm tracing: (1) MCQ — identify the algorithm from an intermediate state (use the fingerprints from this post); (2) NAT — count swaps, comparisons or passes on a ≤ 6-element array; (3) NAT — binary search comparisons or the returned index; (4) MCQ — complexity/stability/in-place facts, or the output of a Python snippet implementing one of these. Practise tracing until a 6-element run takes under two minutes — see the Python & DSA pillar for list slicing and recursion refreshers, and the preparation strategy for how much time this section deserves.

FAQs: Sorting for GATE DA

Keep going: revise Python fundamentals in the Python & DSA pillar, plan the section’s weight with the preparation strategy guide, and track coverage against the GATE DA 2027 syllabus. New problem-solving sessions drop regularly on my YouTube channel — subscribe so you don’t miss them.