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

Source: https://www.techinterview.org/post/3233463353/sorting-algorithm-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## 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](https://techinterview.org/coinbase-software-engineer-interview/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)

## 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.