Quicksort and Mergesort

Analogy categoryAnalogies

Introduction

Quicksort and mergesort are both divide-and-conquer sorting algorithms that achieve O(n log n) time on average, but they differ fundamentally: quicksort partitions the array around a pivot and sorts in-place, while mergesort splits the array in half, recursively sorts each half, and merges the results using auxiliary space. These trade-offs (speed vs. guaranteed complexity, in-place vs. extra memory, unstable vs. stable) make each ideal for different situations.

🏏

Cricket analogy: Quicksort is like a captain setting a batting order by picking one player as a benchmark and splitting the rest above and below him on the spot, while mergesort is like splitting the squad into two nets, drilling each separately, then combining the best XI with extra selectors on hand.

Algorithm/Syntax

python

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

Explanation

Quicksort (Lomuto partition shown above) picks a pivot (here, the last element), partitions the array so smaller elements come before it and larger after, then recursively sorts each side. It runs in O(n log n) on average but degrades to O(n^2) on already-sorted or adversarial input if the pivot is chosen poorly; randomized or median-of-three pivot selection mitigates this. It sorts in-place (O(log n) space for the recursion stack) but is NOT stable because swaps can reorder equal elements. Mergesort instead splits the array into two halves, recursively sorts each, then merges two sorted halves in O(n) time using a temporary array. It guarantees O(n log n) in all cases (best, average, worst) and is stable when the merge step takes from the left half on ties, but it requires O(n) extra space.

🏏

Cricket analogy: Lomuto partition is like picking the last batter's score as the cutoff and shuffling the lineup on the same scoreboard so lower scores sit before it, though equal scores might swap order, while mergesort splits the innings into two halves, sorts each in a separate notebook, and merges them keeping tied scores in original order.

Example

python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:   # <= keeps stability
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Trace: merge_sort([5, 2, 9, 1])
# split -> [5,2] and [9,1]
# [5,2] -> [5] and [2] -> merge -> [2,5]
# [9,1] -> [9] and [1] -> merge -> [1,9]
# merge([2,5], [1,9]) -> [1,2,5,9]
print(merge_sort([5, 2, 9, 1]))  # [1, 2, 5, 9]

Complexity

Quicksort: O(n log n) average, O(n^2) worst case (rare with good pivot choice), O(log n) auxiliary space, in-place, NOT stable, generally fastest in practice due to cache locality and low constant factors. Mergesort: O(n log n) in ALL cases, O(n) auxiliary space, NOT in-place (standard version), stable, preferred for linked lists (O(1) extra space possible there) and external sorting of data too large for memory.

🏏

Cricket analogy: Quicksort is the aggressive stroke-player, fast on average but risky against a well-set bowler (O(n^2) worst case) with minimal extra kit, while mergesort is the steady accumulator, guaranteed to post O(n log n) every innings but needing a bigger support squad, stable, and preferred when reordering a linked chain of overs or huge archived scorecards.

Key Takeaways

Quicksort: O(n log n) average / O(n^2) worst, in-place, unstable, fast in practice.
Mergesort: O(n log n) guaranteed always, O(n) extra space, stable.
Randomized pivot selection avoids quicksort's worst case on sorted/adversarial input.
Mergesort is preferred when stability or guaranteed worst-case performance is required (e.g., external sorting).

Practice what you learned

1. What is the worst-case time complexity of quicksort with a poor pivot choice?

2. Why is mergesort considered stable?

3. How much auxiliary space does standard mergesort require?

4. Which technique helps quicksort avoid its worst-case behavior on sorted input?

5. Which algorithm is generally preferred for sorting linked lists?

Was this page helpful?

Sorting Algorithms Overview

Heap Sort and Counting Sort

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#QuicksortAndMergesort#Quicksort#Mergesort#Algorithm#Syntax#StudyNotes#SkillVeris