DSA • Advanced Sorting

Merge, Quick & Heap Sort

Divide & conquer and tree‑based sorting: understand recursive splitting, partitioning, and heap‑based selection with pseudocode, analysis, and comparative insights.

Algorithms
1
2
3

📌 Advanced Sorting: Moving beyond O(n²) iterative sorts, these three algorithms achieve O(n log n) average time complexity. Merge Sort uses the divide‑and‑conquer paradigm, Quick Sort is a fast in‑place partition‑based sort, and Heap Sort leverages a binary heap data structure.

🎯 What you'll learn: Pseudocode, time/space complexity, stability, in‑place behaviour, pivot strategies (Quick Sort), heapify process (Heap Sort), and a comparative matrix to choose the right algorithm.

01
🔗

Merge Sort

stable divide merge
02
⚡

Quick Sort

unstable pivot in‑place
03
🏔️

Heap Sort

unstable heapify in‑place

1 Merge Sort StableNot In‑place

How it works: Recursively splits the array into two halves until each subarray has one element, then merges them back together in sorted order. The merging step is the core: two sorted arrays are combined into one.

🔗 Merge Sort — Pseudocode Infographic
function mergeSort(arr, left, right): if left < right: mid = (left + right) // 2 mergeSort(arr, left, mid) mergeSort(arr, mid+1, right) merge(arr, left, mid, right) function merge(arr, l, m, r): create temp arrays L = arr[l..m], R = arr[m+1..r] i = 0, j = 0, k = l while i < len(L) and j < len(R): if L[i] <= R[j]: arr[k++] = L[i++] else: arr[k++] = R[j++] copy remaining elements of L and R

Complexity Analysis

CaseTime ComplexitySpace Complexity
BestO(n log n)O(n) (auxiliary)
AverageO(n log n)O(n)
WorstO(n log n)O(n)

Stability: ✅ Stable – merging preserves order of equal elements.
In‑place: ❌ Requires extra space proportional to the input.

💡 Key Insight: Merge Sort is the best choice when stability is required and O(n) extra memory is acceptable. It guarantees O(n log n) even in the worst case, unlike Quick Sort.

2 Quick Sort UnstableIn‑place

How it works: Chooses a pivot element and partitions the array so that elements less than pivot come before it and elements greater come after. Recursively sorts the subarrays. The partition step is the heart of the algorithm.

⚡ Quick Sort — Pseudocode (Lomuto Partition) Infographic
function quickSort(arr, low, high): if low < high: pi = partition(arr, low, high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) function partition(arr, low, high): pivot = arr[high] // last element i = low - 1 for j = low to high-1: if arr[j] < pivot: i++ swap arr[i] and arr[j] swap arr[i+1] and arr[high] return i+1

Complexity Analysis

CaseTime ComplexitySpace Complexity
Best (balanced partitions)O(n log n)O(log n) (stack)
AverageO(n log n)O(log n)
Worst (sorted / reverse)O(n²)O(n) (stack)

Stability: ❌ Unstable – partitioning may swap equal elements.
In‑place: ✅ Yes, only recursive stack space used.

⚠️ Pivot Choice Matters: Worst‑case O(n²) occurs with poor pivot (e.g., first/last element on sorted data). Use random pivot or median‑of‑three to mitigate this.

3 Heap Sort UnstableIn‑place

How it works: First builds a max‑heap from the input array, then repeatedly extracts the maximum element (root) and places it at the end of the array, reducing the heap size by one each time. Relies on the heapify procedure.

🏔️ Heap Sort — Pseudocode Infographic
function heapSort(arr): n = length(arr) // Build max heap for i from n//2 - 1 down to 0: heapify(arr, n, i) // Extract elements one by one for i from n-1 down to 1: swap arr[0] and arr[i] heapify(arr, i, 0) function heapify(arr, n, i): largest = i left = 2*i + 1 right = 2*i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: swap arr[i] and arr[largest] heapify(arr, n, largest)

Complexity Analysis

CaseTime ComplexitySpace Complexity
BestO(n log n)O(1)
AverageO(n log n)O(1)
WorstO(n log n)O(1)

Stability: ❌ Unstable – heap operations may change relative order.
In‑place: ✅ Yes, no extra array needed.

💡 Key Insight: Heap Sort is the only O(n log n) sort that is both in‑place and not recursive (low stack overhead). It guarantees worst‑case performance but is often slower in practice than Quick Sort due to cache inefficiency.

Comparative Analysis

All three achieve O(n log n) average time, but differ in space usage, stability, and worst‑case behaviour. Here’s the definitive comparison:

Property Merge Sort Quick Sort Heap Sort
Average TimeO(n log n)O(n log n)O(n log n)
Worst TimeO(n log n)O(n²)O(n log n)
SpaceO(n)O(log n) (stack)O(1)
Stable✅❌❌
In‑place❌✅✅
Adaptive❌✅ (with proper pivot)❌
Preferred forExternal sorting, linked listsGeneral purpose, small overheadMemory‑constrained, worst‑case guarantee

DSA Questions & Drills

Apply your understanding with these classic problems.

🔰 Beginner Level

1. Implement Merge Sort for an array of strings

Problem: Write a function that sorts a list of words alphabetically using Merge Sort.

def merge_sort_strings(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        merge_sort_strings(L)
        merge_sort_strings(R)
        i=j=k=0
        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                arr[k] = L[i]
                i+=1
            else:
                arr[k] = R[j]
                j+=1
            k+=1
        while i < len(L): arr[k]=L[i]; i+=1; k+=1
        while j < len(R): arr[k]=R[j]; j+=1; k+=1
    return arr
2. Quick Sort with random pivot

Problem: Modify Quick Sort to use a randomly chosen pivot to avoid worst‑case on sorted input.

import random
def quick_sort_random(arr, low, high):
    if low < high:
        pi = partition_random(arr, low, high)
        quick_sort_random(arr, low, pi-1)
        quick_sort_random(arr, pi+1, high)
def partition_random(arr, low, high):
    pivot_idx = random.randint(low, high)
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    pivot = arr[high]
    i = low-1
    for j in range(low, high):
        if arr[j] <= pivot:
            i+=1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1
3. Build a max‑heap from an array and extract top K

Problem: Given an unsorted list, use heap operations to find the 3 largest elements.

import heapq
def top_3(arr):
    heapq.heapify(arr)          # min-heap
    return heapq.nlargest(3, arr)
# Or manually with max-heap using negative values

⚡ Intermediate Level

4. Count inversions using Merge Sort

Problem: Modify Merge Sort to count the number of inversions (i arr[j]).

def merge_count(arr, temp, left, mid, right):
    i = left; j = mid+1; k = left; inv = 0
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]; i+=1
        else:
            temp[k] = arr[j]; inv += (mid-i+1); j+=1
        k+=1
    while i <= mid: temp[k] = arr[i]; i+=1; k+=1
    while j <= right: temp[k] = arr[j]; j+=1; k+=1
    for x in range(left, right+1): arr[x] = temp[x]
    return inv
def merge_sort_inv(arr, temp, left, right):
    inv = 0
    if left < right:
        mid = (left+right)//2
        inv += merge_sort_inv(arr, temp, left, mid)
        inv += merge_sort_inv(arr, temp, mid+1, right)
        inv += merge_count(arr, temp, left, mid, right)
    return inv
5. Kth largest element using Quick Select (derived from Quick Sort)

Problem: Find the Kth largest element in average O(n) using partitioning.

def kth_largest(arr, k):
    def quick_select(low, high):
        pivot = arr[high]
        i = low
        for j in range(low, high):
            if arr[j] >= pivot:  # for largest
                arr[i], arr[j] = arr[j], arr[i]
                i+=1
        arr[i], arr[high] = arr[high], arr[i]
        if i == k-1: return arr[i]
        elif i > k-1: return quick_select(low, i-1)
        else: return quick_select(i+1, high)
    return quick_select(0, len(arr)-1)

Unsolved Practice

Test yourself: implement these without peeking at the solution.

1. Merge Sort on a linked list (without extra space)

Problem: Sort a singly linked list using merge sort. You should split the list recursively and merge without auxiliary arrays. (Hint: find middle, break link, merge sorted halves.)

Write your solution here.
2. Iterative Quick Sort (without recursion)

Problem: Implement Quick Sort using an explicit stack to simulate recursion. Push subarray boundaries onto the stack.

Write your solution here.
3. Heap Sort in descending order (min‑heap version)

Problem: Modify heap sort to sort an array in descending order by building a min‑heap and extracting minimum each time.

Write your solution here.