Sorting Algorithm Interview Patterns: Quicksort, Merge Sort, Counting Sort, Custom Sort

Sorting Algorithm Interview Patterns

While most interviews don’t ask you to implement sorting from scratch, understanding the algorithms helps you choose the right sort for a given problem, explain time/space trade-offs, and solve custom comparison problems.

Coinbase Interview Guide

Atlassian Interview Guide

Uber Interview Guide

LinkedIn Interview Guide

Apple Interview Guide

Meta Interview Guide

Quicksort

Average O(N log N), worst O(N^2) (sorted input with bad pivot). O(log N) space (call stack). In-place. Fastest in practice due to cache locality.

def quicksort(arr, lo, hi):
    if lo >= hi: return
    pivot = partition(arr, lo, hi)
    quicksort(arr, lo, pivot - 1)
    quicksort(arr, pivot + 1, hi)

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

Randomized pivot: pick a random element as pivot to avoid O(N^2) worst case on sorted input. Python’s TimSort (hybrid merge + insertion) is used in production — never actually O(N^2) in practice.

Merge Sort

O(N log N) always. O(N) auxiliary space. Stable (preserves relative order of equal elements). Best for: external sort (data doesn’t fit in memory), stable sort requirements, linked lists (no random access needed).

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, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]: result.append(left[i]); i += 1
        else: result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

Counting Sort / Radix Sort

Counting sort: O(N + K) where K = range of values. Only for integers in a known range. Use when N is large but K is small (e.g., sort 1M numbers all in range 0-1000).

Radix sort: O(N * d) where d = number of digits. Sort integers digit by digit using counting sort. O(N) for fixed-width integers. Use for very large N with bounded integer values.

Custom Sort — Comparator

import functools

# Sort by custom comparison:
# Largest number: concatenation order
def largest_number(nums):
    def cmp(a, b):
        return 1 if str(a)+str(b) < str(b)+str(a) else -1
    nums.sort(key=functools.cmp_to_key(cmp))
    return '0' if nums[0] == 0 else ''.join(map(str, nums))

Partial Sort — Top-K with Quickselect

def quickselect(arr, k):
    """Find kth smallest in O(N) average."""
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        pivot = partition(arr, lo, hi)
        if pivot == k: break
        elif pivot < k: lo = pivot + 1
        else: hi = pivot - 1
    return arr[k]

Dutch National Flag (3-way partition)

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

Interview Tips

• Stability matters when sorting objects by one key when they’re already sorted by another (e.g., sort by last name, then by first name stably).
• External sort: split file into M chunks that fit in RAM, sort each, K-way merge on disk.
• Custom comparator: use functools.cmp_to_key in Python to convert a comparator to a key function.
• Quickselect for Kth element: O(N) average, O(1) extra space — faster than heap O(N log K) when K ≈ N/2.