Sorting Algorithms

Why Sorting Matters

Searching in a sorted array takes O(log n) instead of O(n). Sorting is a prerequisite for binary search, merge operations, and many real-world applications like database indexing.

The Big Comparison Table

Algorithm	Best	Average	Worst	Space	Stable?	In-place?
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No	Yes
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Yes
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Yes

Key GATE traps: - Insertion sort is O(n) for nearly sorted input — best for small/nearly-sorted arrays - Heap sort is in-place but NOT stable - Quick sort worst case is sorted input with naive pivot (first element)

Merge Sort — Step by Step

Idea: Divide array in half, sort each half, then merge two sorted halves.

Sort [38, 27, 43, 3, 9, 82, 10]:

Divide:         [38,27,43,3]    [9,82,10]
Divide:     [38,27]  [43,3]   [9,82]  [10]
Divide:   [38][27]  [43][3] [9][82]  [10]

Merge up:
   [27,38]   [3,43]   [9,82]   [10]
       [3,27,38,43]   [9,10,82]
             [3,9,10,27,38,43,82]  ✓

Recurrence: T(n) = 2T(n/2) + n → Θ(n log n) by Master Theorem Case 2.

Why O(n) space? The merge step needs a temporary array of size n to hold merged results.

Quick Sort — Step by Step

Idea: Pick a "pivot." Put all smaller elements left, larger right, then recursively sort left and right.

Sort [3, 6, 8, 10, 1, 2, 1] with pivot = last element (1):

Partition around 1:
Elements < 1: none
Pivot: 1
Elements > 1: [3, 6, 8, 10, 2, 1]  ← oops, another 1!

After partition: [1, 1, 3, 6, 8, 10, 2]  (approximately)

Recursively sort left of pivot and right of pivot.

Why worst case O(n²)? If input is already sorted and we always pick first element as pivot:

[1, 2, 3, 4, 5] with pivot=1:
Partition: [1] [2,3,4,5]  ← one side has 0 elements, other has n-1
Next level: pivot=2, partition [2] [3,4,5]  ...

This creates n levels each doing O(n) work → O(n²)

Fix: Use random pivot or median-of-three pivot to avoid worst case in practice.

Heap Sort — Using the Heap Structure

Build a max-heap from the array: O(n) — recall Build-heap is linear!
Extract max n times, placing each max at the end of the array: O(n log n)

Initial: [4, 10, 3, 5, 1] Build max-heap: [10, 5, 3, 4, 1]

Extract 10 → put at end: [5, 4, 3, 1, |10] Extract 5 → put at end: [4, 1, 3, |5, 10] Extract 4 → put at end: [3, 1, |4, 5, 10] ... Final sorted: [1, 3, 4, 5, 10] ✓

Total: O(n) + O(n log n) = O(n log n). In-place (sorts within the original array). NOT stable (swapping disrupts relative order).

Why Comparison Sorting Cannot Be Better Than O(n log n)

Any comparison-based sort must make enough comparisons to determine the correct order.

There are n! possible orderings of n elements. Each comparison rules out half the possibilities (like a yes/no question in 20 questions).

Number of comparisons needed ≥ log₂(n!)
By Stirling's approximation: log₂(n!) ≈ n log₂(n) − n log₂(e) = Ω(n log n)

So no comparison sort can beat Ω(n log n) in the worst case.

Non-Comparison Sorts — Breaking the Barrier

These algorithms don't compare elements — they use the structure of the keys.

Counting Sort: O(n + k) where k = max value - Count frequency of each value, then reconstruct sorted array. - Requires integer keys in range [0, k]. - Stable.

Input: [1, 4, 1, 2, 7, 5, 2]
Count: [0, 2, 2, 0, 1, 1, 0, 1]  (count[i] = how many times i appears)
Output: [1, 1, 2, 2, 4, 5, 7] ✓

Radix Sort: O(d × (n + k)) - Sort digit by digit from least significant to most significant (LSD radix sort). - Each digit pass uses counting sort (must be stable!). - d = number of digits, k = digit range (usually 10).

Sort [170, 045, 075, 090, 802, 024, 002, 066]:

By ones:  [170, 090, 802, 002, 024, 045, 075, 066]
By tens:  [802, 002, 024, 045, 066, 170, 075, 090]
By hunds: [002, 024, 045, 066, 075, 090, 170, 802] ✓

What is "Stable"?

A sort is stable if equal elements maintain their original relative order.

Input: [(A,2), (B,1), (C,2), (D,1)]  (sort by number)

Stable output:   [(B,1), (D,1), (A,2), (C,2)]  ← B before D, A before C
Unstable output: [(D,1), (B,1), (C,2), (A,2)]  ← relative order changed

Stability matters when sorting on multiple keys (sort by department, then by salary within department).

Quick Check

Q1. Which sorting algorithm is best for an almost-sorted array of 100 elements?

Answer: Insertion sort — O(n) for nearly sorted input, and low overhead for small n.

Q2. Merge sort vs Quick sort — which guarantees O(n log n) worst case?

Answer: Merge sort — Quick sort degrades to O(n²) on sorted input with bad pivot.

Q3. Is heap sort stable?

Answer: No — heap operations can change the relative order of equal elements.

Key Points