Sorting Algorithms: When to Use Which, and Why Interviewers Still Ask About Them

"Implement merge sort" is a staple interview question — not because you'll write sorting algorithms at work, but because sorting is the perfect lens for evaluating algorithmic thinking. It tests recursion, divide-and-conquer, time/space trade-offs, and stability in one tidy package.

This guide covers every sorting algorithm you need for interviews, when to reach for each one, and the deeper questions interviewers are really asking.

---

Why Sorting Still Matters in 2026

Three reasons sorting appears constantly in interviews:

1. It's a prerequisite for other algorithms. Binary search requires sorted input. Many two-pointer and greedy solutions sort first. Understanding sorting unlocks 30% of DSA problems.

2. It teaches trade-offs. Every sorting algorithm sacrifices something — time for space, simplicity for speed, general-purpose for special-case. Explaining these trade-offs is the real interview skill.

3. The "implement it" question reveals depth. Merge sort and quicksort require recursion, divide-and-conquer, and careful index handling. Getting them right from scratch is genuinely hard under pressure.

---

The Comparison

| Algorithm | Time (avg) | Time (worst) | Space | Stable | When to use | |---|---|---|---|---|---| | Bubble Sort | O(n²) | O(n²) | O(1) | ✅ | Never in production; only for teaching | | Selection Sort | O(n²) | O(n²) | O(1) | ❌ | Never; fewer swaps than bubble sort | | Insertion Sort | O(n²) | O(n²) | O(1) | ✅ | Small or nearly-sorted arrays | | Merge Sort | O(n log n) | O(n log n) | O(n) | ✅ | Linked lists; when stability needed | | Quick Sort | O(n log n) | O(n²) | O(log n) | ❌ | General-purpose; cache-friendly | | Heap Sort | O(n log n) | O(n log n) | O(1) | ❌ | Guaranteed O(n log n) + O(1) space | | Counting Sort | O(n + k) | O(n + k) | O(k) | ✅ | Integers in a small range | | Radix Sort | O(nk) | O(nk) | O(n + k) | ✅ | Fixed-width integers or strings |

Stability means equal elements maintain their original relative order. Matters when sorting objects by one key when they're already sorted by another.

---

Insertion Sort — The Underrated One

Bubble and selection sort are only useful as teaching tools. Insertion sort is actually practical: it runs in O(n) on nearly-sorted input, has zero overhead, and is the algorithm Python uses internally for small subarrays.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Shift elements larger than key one position to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

How it works: Think of building a sorted hand of cards. You pick up each new card and slide it left until it's in the right position.

When it's optimal: Arrays with fewer than ~20 elements. Streams where you insert one element at a time. Nearly-sorted arrays (O(n) in the best case).

---

Merge Sort — The Reliable Workhorse

Merge sort is the algorithm every interviewer expects you to implement from scratch. It's O(n log n) always — no worst case surprises — and it's stable.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # sort left half
    right = merge_sort(arr[mid:])  # sort right half
    
    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]:   # <= preserves stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

The recursion:

merge_sort([5, 3, 8, 1, 9, 2])
  → merge_sort([5, 3, 8]) and merge_sort([1, 9, 2])
      → merge_sort([5]) and merge_sort([3, 8])
          → merge([5], merge_sort([3, 8]))
              → merge([5], merge([3], [8]))
              → merge([5], [3, 8])
              → [3, 5, 8]
      ...
  → merge([3, 5, 8], [1, 2, 9])
  → [1, 2, 3, 5, 8, 9]

Space: O(n) for the temporary arrays. This is merge sort's main weakness vs quicksort.

Best use case: Sorting linked lists (no random access → quicksort's performance degrades). External sorting (data too large for memory — merge chunks from disk).

Counting Inversions (a merge sort application)

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Counting inversions in O(n log n) is a classic hard problem solved by modifying merge sort:

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    
    mid = len(arr) // 2
    left, left_inv = count_inversions(arr[:mid])
    right, right_inv = count_inversions(arr[mid:])
    
    merged = []
    inversions = left_inv + right_inv
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            # All remaining elements in left are > right[j]
            inversions += len(left) - i
            merged.append(right[j])
            j += 1
    
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversions

---

Quick Sort — The Fastest in Practice

Quicksort is faster than merge sort in practice because of cache locality — it sorts in-place, accessing contiguous memory. Python's built-in sorted() uses Timsort (a merge sort + insertion sort hybrid), but C++ std::sort uses introsort (quicksort + heap sort hybrid).

def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        pivot_idx = partition(arr, low, high)
        quicksort(arr, low, pivot_idx - 1)
        quicksort(arr, pivot_idx + 1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]   # choose last element as pivot
    i = low - 1         # boundary of smaller elements
    
    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

Why worst case is O(n²): If the pivot is always the smallest or largest element (sorted input with last-element pivot), every partition splits the array into sizes 0 and n-1. Depth becomes O(n) instead of O(log n).

Fix with random pivot:

import random

def partition_random(arr, low, high):
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    return partition(arr, low, high)

Random pivot reduces worst-case probability to essentially zero in practice.

---

Heap Sort — O(1) Space Guarantee

Heap sort is rarely used in production but often asked in interviews because it proves you understand heaps.

def heap_sort(arr):
    n = len(arr)
    
    # Build a max-heap (in-place)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # move max to end
        heapify(arr, i, 0)               # restore heap on reduced array
    
    return arr

def 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:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

When to choose heap sort: When you need guaranteed O(n log n) worst case AND O(1) extra space. In practice, quicksort with random pivot is usually preferred.

---

Counting Sort and Radix Sort — Linear Time

For specific inputs, you can beat O(n log n). The key: these algorithms don't compare elements — they exploit the structure of the data.

Counting Sort

Works when all values are non-negative integers within a known range.

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    
    for num in arr:
        count[num] += 1
    
    result = []
    for val, freq in enumerate(count):
        result.extend([val] * freq)
    
    return result

# Example: sort [4, 2, 2, 8, 3, 3, 1]
# count = [0, 1, 2, 2, 1, 0, 0, 0, 1]  (index = value, cell = frequency)
# output = [1, 2, 2, 3, 3, 4, 8]

When to use: Ages (0-150), scores (0-100), character frequencies. Fails when range k is huge (counting sort for 64-bit integers would need 2^64 buckets).

Radix Sort

Sort integers digit by digit from least significant to most significant, using counting sort on each digit.

def radix_sort(arr):
    max_val = max(arr)
    exp = 1  # current digit position (1, 10, 100, ...)
    
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # digits 0-9
    
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1
    
    # Cumulative count (stable positioning)
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Build output right-to-left (for stability)
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    
    for i in range(n):
        arr[i] = output[i]

When to use: Phone numbers, ZIP codes, fixed-length strings. O(nk) where k is the number of digits.

---

The Interview Questions Sorting Unlocks

Knowing sorting deeply opens these problems:

"Sort colors" (Dutch National Flag): Three-way partition — O(n), O(1) space.

def sort_colors(nums):
    low = mid = 0
    high = len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

"Kth Largest Element": Quickselect — O(n) average, no need to sort fully.

"Meeting Rooms II": Sort intervals by start time, then use a min-heap on end times.

"Merge Intervals": Sort by start, then scan linearly.

---

What Interviewers Are Really Asking

When an interviewer says "implement merge sort," they're checking:

• Can you write correct recursion with proper base cases?
• Do you understand the merge step — specifically the two-pointer pattern?
• Can you reason about why it's O(n log n) and O(n) space?
• Do you know when to use it vs quicksort?

When they say "sort this array of integers from 1 to 1000," they want to hear "counting sort — O(n + k), not comparison-based."

That last answer — recognising when NOT to use a general-purpose sort — is what separates strong candidates from average ones.

Practice target: Implement merge sort and quicksort from scratch without referring to notes. Time yourself. If it takes more than 10 minutes, practice again. Then solve Sort Colors and Kth Largest Element in Practice.