Sorting Algorithms

Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

​

Overview

​

Pattern Recognition Cheatsheet

​

Universal Templates

# TEMPLATE 1: Quicksort (in-place, O(n log n) average, O(n^2) worst)
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)

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

# TEMPLATE 2: Mergesort (stable, O(n log n) guaranteed, O(n) extra space)
def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return merge(left, right)

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

# TEMPLATE 3: Custom comparator (LeetCode 179, 937, etc.)
from functools import cmp_to_key
# Sort by key (preferred -- stable, O(n log n))
sorted(arr, key=lambda x: (x.priority, x.name))
# Sort by full pairwise comparator (slower -- use only when key trick is infeasible)
def compare(a, b):
    return -1 if a + b > b + a else 1     # for "Largest Number" problem
sorted(arr, key=cmp_to_key(compare))

​

When to Choose Which

​

Algorithm Implementations

​

1. Quick Sort

def quick_sort(arr, low=0, high=None):
    """Average O(n log n), in-place, unstable"""
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
    
    return arr

def partition(arr, low, high):
    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

​

2. Merge Sort

def merge_sort(arr):
    """O(n log n), stable, O(n) space"""
    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]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

​

3. Heap Sort

def heap_sort(arr):
    """O(n log n), in-place, unstable"""
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    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)

​

4. Counting Sort

def counting_sort(arr):
    """O(n + k), stable, for small range integers"""
    if not arr:
        return arr
    
    min_val, max_val = min(arr), max(arr)
    range_size = max_val - min_val + 1
    
    count = [0] * range_size
    output = [0] * len(arr)
    
    # Count occurrences
    for num in arr:
        count[num - min_val] += 1
    
    # Cumulative count
    for i in range(1, range_size):
        count[i] += count[i - 1]
    
    # Build output (reverse for stability)
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    
    return output

​

Complexity Comparison

​

Worked LeetCode Problems

​

LC 215 — Kth Largest Element in an Array (Medium)

import heapq
def findKthLargest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)        # discard smallest -- keep top K
    return heap[0]                      # root is kth largest

import random
def findKthLargest(nums, k):
    target = len(nums) - k             # kth largest = (n-k)th smallest by index

    def quickselect(lo, hi):
        pivot = nums[random.randint(lo, hi)]
        # three-way partition for robustness against duplicates
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[gt], nums[i] = nums[i], nums[gt]
                gt -= 1
            else:
                i += 1
        if target < lt:
            return quickselect(lo, lt - 1)
        elif target > gt:
            return quickselect(gt + 1, hi)
        else:
            return nums[target]

    return quickselect(0, len(nums) - 1)

​

LC 56 — Merge Intervals (Medium)

def merge(intervals):
    intervals.sort(key=lambda x: x[0])     # sort by start
    result = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= result[-1][1]:          # overlap with last merged interval
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result

​

LC 252 / 253 — Meeting Rooms I & II (Easy / Medium)

def canAttendMeetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True

import heapq
def minMeetingRooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []                                # holds end times of in-use rooms
    for start, end in intervals:
        if heap and heap[0] <= start:        # earliest-ending room is free
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

def minMeetingRooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    rooms = used = j = 0
    for start in starts:
        if start < ends[j]:
            used += 1                        # need a new room
            rooms = max(rooms, used)
        else:
            j += 1                           # a meeting ended -- reuse its room
    return rooms

​

LC 75 — Sort Colors / Dutch National Flag (Medium)

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    # invariant:
    #   nums[0..low-1]       == 0
    #   nums[low..mid-1]     == 1
    #   nums[mid..high]      unprocessed
    #   nums[high+1..end]    == 2
    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] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # do NOT advance mid -- the swapped-in value is unprocessed

​

Curated LeetCode List

​

Interview Q&A — Senior-Level Walkthroughs

def sortColors(nums):
    low, mid, high = 0, 0, 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] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # critically: do NOT advance mid here

import heapq
def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            # tuple: (value, tiebreaker_index, node)
            heapq.heappush(heap, (node.val, i, node))
    dummy = ListNode(0)
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

from functools import cmp_to_key
def largestNumber(nums):
    strs = list(map(str, nums))
    # comparator: a before b if a+b > b+a (we want larger first, so return -1)
    def compare(a, b):
        if a + b > b + a:
            return -1
        elif a + b < b + a:
            return 1
        else:
            return 0
    strs.sort(key=cmp_to_key(compare))
    result = ''.join(strs)
    return '0' if result[0] == '0' else result      # handle [0,0,0] edge case

public String largestNumber(int[] nums) {
    String[] strs = new String[nums.length];
    for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);
    Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));   // descending
    if (strs[0].equals("0")) return "0";
    StringBuilder sb = new StringBuilder();
    for (String s : strs) sb.append(s);
    return sb.toString();
}

import random
def findMedian(nums):
    n = len(nums)
    target = n // 2

    def quickselect(lo, hi):
        pivot = nums[random.randint(lo, hi)]
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[gt], nums[i] = nums[i], nums[gt]
                gt -= 1
            else:
                i += 1
        if target < lt:
            return quickselect(lo, lt - 1)
        elif target > gt:
            return quickselect(gt + 1, hi)
        else:
            return nums[target]

    if n % 2 == 1:
        return quickselect(0, n - 1)
    else:
        # for even n, average the two middle values
        a = quickselect(0, n - 1)
        target = n // 2 - 1
        b = quickselect(0, n - 1)
        return (a + b) / 2

​

Practice Problems

​

Interview Questions

​

1. Compare Quick Sort and Merge Sort. When would you choose one over the other?

• Both are O(n log n) on average, but the trade-offs matter in practice. Merge Sort guarantees O(n log n) in all cases and is stable (equal elements preserve order), but requires O(n) extra space for the merge buffer. Quick Sort is O(n log n) average with O(n^2) worst case, but it sorts in-place with only O(log n) stack space and has excellent cache locality because it operates on contiguous memory.
• Choose Merge Sort when stability is required (sorting objects by multiple keys), when working with linked lists (no random access needed, and the merge step uses O(1) extra space on linked lists), or when you need a worst-case guarantee (external sorting, real-time systems).
• Choose Quick Sort for in-memory arrays where average-case speed matters. Quick Sort typically outperforms Merge Sort by 2-3x in practice due to better cache behavior — the partition step accesses elements sequentially in memory, while Merge Sort bounces between the input and a temporary buffer.
• The worst case for Quick Sort (already sorted array with last-element pivot) is mitigated with randomized pivot selection or median-of-three. In production code, libraries like Python’s Timsort and Java’s Arrays.sort() for primitives use hybrid approaches — Timsort is a merge-sort/insertion-sort hybrid, and Java uses dual-pivot Quick Sort for primitives.

1. Why is Quick Sort preferred for arrays but Merge Sort preferred for linked lists? What changes about the cost model?
2. Explain how randomized pivot selection prevents the O(n^2) worst case. What is the probability of hitting worst case with random pivots?

​

2. What does it mean for a sorting algorithm to be “stable,” and why does it matter in practice?

• A stable sort preserves the relative order of elements that compare as equal. If two records have the same sort key, they appear in the output in the same order they appeared in the input.
• In practice, this matters when sorting by multiple criteria. Suppose you have a list of employees sorted by name, and you then sort by department. With a stable sort, employees within each department remain alphabetically sorted. With an unstable sort, the name ordering within each department is destroyed.
• Among the classic comparison sorts: Merge Sort is stable, Quick Sort and Heap Sort are not. Counting Sort and Radix Sort are stable by design, which is why Radix Sort works — it relies on the stability of its inner counting sort passes.
• Real-world example: database ORDER BY clauses with multiple columns rely on stable sorting. Python’s sort() is stable (Timsort), which is why you can sort by secondary key first, then primary key, and get the correct multi-key ordering.

1. Can you make an unstable sort stable? What is the cost?
2. Why is Heap Sort unstable? Can you give a concrete example where it reorders equal elements?

​

3. Explain Counting Sort. When is it faster than comparison-based sorts, and when does it fail?

• Counting Sort works by counting the frequency of each value, then using cumulative counts to place each element directly into its correct position. It runs in O(n + k) time where k is the range of input values (max - min + 1). It does not compare elements at all — it uses values as array indices.
• It beats comparison sorts when k is O(n) or smaller. Sorting 1 million integers all in the range [0, 1000]? Counting Sort runs in O(n) while Quick Sort needs O(n log n). Sorting exam scores (0-100) for 10,000 students? Counting Sort is clearly superior.
• It fails when the range k is much larger than n. Sorting 100 integers in the range [0, 10^9] requires a count array of a billion entries — wildly impractical. It also only works on discrete values (integers or values that can be mapped to integers), not floating-point numbers or arbitrary objects.
• The stable version iterates through the input in reverse order when building the output, using the cumulative count to determine each element’s position. This is important because Radix Sort depends on Counting Sort being stable.

1. How does Radix Sort use Counting Sort internally? What is Radix Sort’s total complexity?
2. There is a theorem that comparison-based sorting cannot be faster than O(n log n). How is Counting Sort not violating this?

​

4. You are given an array of intervals like [[1,3], [2,6], [8,10], [15,18]]. Merge all overlapping intervals. Walk through your approach.

• First, sort the intervals by their start time. This ensures that any overlapping intervals are adjacent in the sorted order, which turns the problem from a global check into a local one.
• Then do a single linear scan: maintain a current interval. For each next interval, if it overlaps with current (next.start <= current.end), merge them by extending current.end to max(current.end, next.end). If it does not overlap, push current to the result and start a new current.
• Time is O(n log n) for the sort plus O(n) for the scan. Space is O(n) for the output (or O(log n) for the sort stack, depending on what counts).
• Edge cases: intervals that are fully contained within another (like [1,10] and [2,3] — the merge just keeps [1,10]), intervals that share a single boundary point ([1,3] and [3,5] merge into [1,5]), and a single interval (return as-is).

1. What if instead of merging you need to find the minimum number of meeting rooms required for a set of time intervals? How does sorting help?
2. How would you insert a new interval into an already sorted, non-overlapping list and merge if necessary?

​

5. Explain the Dutch National Flag algorithm (three-way partitioning). Why is it useful beyond just sorting?

• The Dutch National Flag algorithm partitions an array into three regions around a pivot value: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. It uses three pointers — low, mid, and high — and processes the array in a single O(n) pass.
• The invariant: everything before low is less than the pivot, everything between low and mid is equal, everything after high is greater, and between mid and high is unprocessed. We advance mid and swap elements to maintain this invariant.
• For “Sort Colors” (LeetCode 75), the three values are 0, 1, and 2. The pivot is 1. After one pass: all 0s are on the left, 1s in the middle, 2s on the right.
• Beyond Sort Colors, three-way partitioning is the fix for Quick Sort with many duplicates. Standard Lomuto partition puts equal elements on one side, leading to O(n^2) when all elements are the same. Three-way partition groups equals together and only recurses on the less-than and greater-than partitions, restoring O(n log n) performance.

1. Walk me through the pointer movements for the array [2, 0, 1, 2, 0, 1] step by step.
2. How does Quick Sort’s performance degrade with many duplicate keys, and how does three-way partitioning fix it?

​

6. What is Quick Select and how does it find the kth largest element in O(n) average time?

• Quick Select uses Quick Sort’s partition step, but instead of recursing on both halves, it only recurses on the half that contains the kth element. After partitioning, the pivot is at its final sorted position p. If p == k, we are done. If k < p, recurse on the left half. If k > p, recurse on the right half.
• Average time is O(n): the recurrence is T(n) = T(n/2) + O(n), which sums to O(2n) = O(n). This is because each recursive call cuts the problem roughly in half, and the total work across all levels forms a geometric series.
• Worst case is O(n^2) for the same reason as Quick Sort — a bad pivot picks the smallest or largest element every time. Mitigation: use randomized pivot selection or the “median of medians” algorithm for a guaranteed O(n) worst case (though the constant factor is large, so randomized is preferred in practice).
• Real-world usage: finding the median of an unsorted array, finding percentiles, the kth smallest in a stream. C++‘s std::nth_element uses a variant of this algorithm.

1. What is the “median of medians” algorithm? How does it guarantee O(n) worst case, and why is it rarely used in practice?
2. If you needed the kth largest element from a continuous stream of data, would Quick Select still work? What would you use instead?

​

7. Why do most standard library implementations use hybrid sorting algorithms instead of a pure Quick Sort or Merge Sort?

• Hybrid sorts combine the strengths of multiple algorithms to handle different input sizes and patterns. Python’s Timsort (used in list.sort() and Java’s Arrays.sort() for objects) is a merge-sort/insertion-sort hybrid. It detects already-sorted subsequences (“runs”) in the data and merges them, achieving O(n) on nearly-sorted input while maintaining O(n log n) worst case.
• For small subarrays (typically n under 16 to 32), all O(n log n) algorithms are slower than Insertion Sort because the overhead of recursion, function calls, and cache misses dominates. So hybrid sorts switch to Insertion Sort below a threshold.
• Java uses dual-pivot Quick Sort for primitive arrays (better cache behavior, in-place) and Timsort for object arrays (stability required for objects since equals() behavior must be preserved).
• Introsort (used in C++ std::sort) starts with Quick Sort, monitors recursion depth, and switches to Heap Sort if the depth exceeds 2 * log(n) — this prevents the O(n^2) worst case while getting Quick Sort’s cache benefits in the average case.

1. What is the significance of “runs” in Timsort? How does it exploit partially sorted data?
2. If you were implementing a sort for a database engine that needs to sort data larger than memory, which algorithm would you choose and why?