Sorting Field Notes

0Why four sorts, not one

Sorting means "rearrange a list so each item is less than or equal to the next one". Every sort in this topic is built from two moves: compare two values, and move a value. The four algorithms differ in which values they compare and how far they move them. That choice decides the running time, the memory used, and whether equal items keep their original order.

The videos build the algorithms in this order because each one fixes a weakness of the one before. Insertion sort is simple but O(n²). Merge sort is O(n log n) always, but needs extra memory. Quick sort is O(n log n) on average with no extra memory, but can degrade to O(n²). Bucket sort is O(n), but only when the values live in a small, known range.

1Insertion sort

Simple, easy to implement and understand. Not efficient for large data sets. It is the sort to learn first because the idea of a sorted portion that grows shows up again in merge sort.

The idea: a sorted part that grows by one

Given [2,3,4,1,6], the goal is [1,2,3,4,6]. Insertion sort sorts portions of the array at a time. An array of size 1 is already sorted (there is nothing to compare it with). So we assume the first element is sorted: it is its own subarray. The next subarray is size 2 from the start, [2,3,...]: compare the two. Then size 3, and so on, until the sorted portion is the whole array.

For the full array we need two pointers, i and j:

• i points at the element we are currently inserting into the sorted portion.
• j starts one index to the left of i.
• Goal: find the position where arr[i] should be inserted into the sorted portion.
• Keep swapping it with arr[j] until we find the correct position; after each swap shift j left by 1.
• Stop once the element is greater than or equal to the element to its left.

def insertionSort(arr):
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        j = i - 1
        while j >= 0 and arr[j + 1] < arr[j]:
            # arr[j] and arr[j + 1] are out of order so swap them
            tmp = arr[j + 1]
            arr[j + 1] = arr[j]
            arr[j] = tmp
            j -= 1
    return arr

The three tmp lines are NeetCode's swap. In Python you write the same thing as one line: arr[j], arr[j+1] = arr[j+1], arr[j]. Both versions are tested.

def insertion_sort_py(arr):
    for i in range(1, len(arr)):
        j = i - 1
        while j >= 0 and arr[j + 1] < arr[j]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]   # tuple swap, no tmp
            j -= 1
    return arr

Note the condition arr[j + 1] < arr[j]. arr[j + 1] is the element we are inserting; it moves left one slot per swap, so its index is always j + 1. This works on any data type as long as two values can be compared: numbers, strings, tuples. Insertion sort is easier to write iteratively; the next two sorts are recursive.

Stability: do equal values keep their order?

Stable means "the relative order of equal elements is preserved after sorting". Take [7,3,7]. There are two 7s, at index 0 and index 2. Call them 7_a and 7_b so we can tell them apart. Pass i=1: 3 swaps with 7_a. Pass i=2: is 7_b < 7_a? No, they are equal, so the while loop stops. The two 7s keep their relative order. Insertion sort is stable. Not all sorts are; quick sort below is not.

Time and space

• Best case, O(n): the array is already sorted. The inner while loop never executes; the outer loop still visits each element once.
• Worst case, O(n²): the inner loop executes up to n times for each of the n elements. The worst-case input is an array sorted in reverse (descending) order: every new element must travel all the way to the front. On [5,4,3,2,1] that is 4 + 3 + 2 + 1 = 10 swaps, and in general n(n-1)/2.
• Average case (random order): still O(n²). On average each element travels about halfway, and n²/4 is still O(n²).
• Space, O(1): it sorts in place (inside the original array) and allocates no additional data structure. Only i, j, tmp.

2Merge sort

Extremely common. Many language standard libraries use it or a variant of it (Python's sorted() is a merge sort hybrid, see Patterns). Idea: keep splitting the array into halves until each subarray has size one, then sort by merging two sorted subarrays at a time, working back up.

This is divide and conquer: divide the problem into subproblems, solve them, then combine the solutions. The recursion has two branches (left half, right half), like Fibonacci from the recursion topic.

mergeSort(): the recursive part is short

# Implementation of MergeSort
def mergeSort(arr, s, e):
    if e - s + 1 <= 1:
        return arr

    # The middle index of the array
    m = (s + e) // 2

    # Sort the left half
    mergeSort(arr, s, m)

    # Sort the right half
    mergeSort(arr, m + 1, e)

    # Merge sorted halfs
    merge(arr, s, m, e)

    return arr

• Base case: length e - s + 1 is 1 or less. Already sorted, return.
• Compute the middle index m = (s + e) // 2.
• Recursively mergeSort the left half s..m and the right half m+1..e.
• Merge the two sorted halves with merge().

s and e are inclusive start and end indexes. You call it as mergeSort(arr, 0, len(arr) - 1). Passing indexes instead of slicing keeps everything in the one original array.

merge(): the three-pointer part does the work

Two sorted halves sit next to each other in arr: s..m and m+1..e. Copy them into temporary lists L and R, then walk both with one pointer each and write the smaller value back into arr.

• k tracks where the next element in arr must be placed. Starts at s.
• i points to the element in the left subarray L being compared to the j element in the right subarray R.
• One of i or j increments depending on which element is smaller; k increments regardless.

# Merge in-place
def merge(arr, s, m, e):
    # Copy the sorted left & right halfs to temp arrays
    L = arr[s: m + 1]
    R = arr[m + 1: e + 1]

    i = 0 # index for L
    j = 0 # index for R
    k = s # index for arr

    # Merge the two sorted halfs into the original array
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # One of the halfs will have elements remaining
    while i < len(L):
        arr[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        arr[k] = R[j]
        j += 1
        k += 1

The same algorithm in idiomatic Python

In interviews people often write the slicing version: it returns a new list instead of sorting in place. Same algorithm, same Big-O, and easier to read. Know both; the index version is what NeetCode shows and it is what you need for the in-place variants.

def merge_sort_py(arr):
    if len(arr) <= 1:
        return arr
    m = len(arr) // 2
    left = merge_sort_py(arr[:m])       # sorted copy of the left half
    right = merge_sort_py(arr[m:])      # sorted copy of the right half
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])                # leftovers, one of these is empty
    out.extend(right[j:])
    return out

Time: O(n log n), and where the log comes from

Count the levels of the recursion. Each level halves the length: n, then n/2, then n/4, ... down to 1. If it takes x halvings to reach 1, then n / 2^x = 1, so n = 2^x, so x = log₂ n. There are log n levels. Now count the cost per level: at any level, the merges together touch every one of the n elements exactly once (compare and place), so each level costs n. Total = levels × cost per level = n log n.

Space: O(n)

Two things use memory. The call stack is as deep as the tree is tall: log n frames. The temporary lists L and R: at any single moment the temp arrays in use add up to at most n elements. Total O(n + log n) = O(n). It is a sum, not a product, because the temp arrays are not all allocated at the same time; each merge() frees its L and R when it returns.

Stability

Merge sort is stable. Look at the comparison: if L[i] <= R[j]. On a tie we take the left element first. Everything in L came before everything in R in the original array, so equal elements keep their relative order. Change <= to < and the sort becomes unstable.

3Quick sort

Another divide and conquer sort. Idea: pick one element and call it the pivot. Partition the array so that every value to the left of the pivot is less than or equal to it, and every value to the right is greater. Then recurse on the left part and on the right part.

Picking a pivot

Options: the first index; the last index; the median of the first, last and middle values; or a random index. Ideally the pivot divides the array into two roughly equal halves, because then the recursion is log n deep. This lesson picks the last element, which keeps the code short.

Recursive partitioning

Partition so that elements <= pivot are on the left and the rest on the right, then recursively quick sort the left part and the right part until the base case (size 1). Unlike merge sort there is no merge step: partitioning alone sorts the array, because after each partition the pivot sits at its final index and nothing ever crosses it again. Quick sort is, in a sense, the opposite of merge sort. Merge sort has a simple recursive step and a complex merge(); quick sort puts the complexity into the partition and has trivial recursion.

Partition example: [6,2,4,1,3], pivot = 3 (the last element). The result has all elements smaller than the pivot on the left and the rest on the right. Then run recursively until the base case. No new memory is allocated; only the s and e indexes change to work on a smaller part of the original array.

# Implementation of QuickSort
def quickSort(arr: list[int], s: int, e: int) -> list[int]:
    if e - s + 1 <= 1:
        return arr

    pivot = arr[e]
    left = s # pointer for left side

    # Partition: elements smaller than pivot on left side
    for i in range(s, e):
        if arr[i] < pivot:
            tmp = arr[left]
            arr[left] = arr[i]
            arr[i] = tmp
            left += 1

    # Move pivot in-between left & right sides
    arr[e] = arr[left]
    arr[left] = pivot

    # Quick sort left side
    quickSort(arr, s, left - 1)

    # Quick sort right side
    quickSort(arr, left + 1, e)

    return arr

Read left as "the first slot that is not yet known to be smaller than the pivot". Every time i finds a small value, it swaps that value into slot left and moves left one to the right. When the loop ends, slots s..left-1 hold the small values, so left is exactly where the pivot belongs.

The recursion then works on each side. Both are size 2, so one more partition each and the array is sorted.

Time and space

The partition loop is O(n) per level: i visits every element once. How many levels? In the best case the pivot is the median and splits the array in the middle every time, so there are log n levels, and the total is O(n log n), the same picture as merge sort's levels diagram. In the worst case the pivot is always the smallest or largest element. Then one side has n - 1 elements and the other has 0. The recursion tree is a chain of height n, each level still doing O(n) partition work: n + (n-1) + (n-2) + ... = O(n²).

Randomized quick sort

The fix is to not let the input decide the pivot. Pick the pivot randomly, or shuffle the array first. A sorted array is then no worse than any other. This gives an expected O(n log n) instead of the typical worst case O(n²). The worst case is still possible, but only by bad luck, not by bad input. The code changes by two lines: swap a random element into the last slot, then partition exactly as before.

import random

def quick_sort_random(arr, s, e):
    if e - s + 1 <= 1:
        return arr
    r = random.randint(s, e)           # any index in s..e
    arr[r], arr[e] = arr[e], arr[r]    # move it to the end, so the rest is unchanged
    pivot = arr[e]
    left = s
    for i in range(s, e):
        if arr[i] < pivot:
            arr[left], arr[i] = arr[i], arr[left]
            left += 1
    arr[e], arr[left] = arr[left], arr[e]
    quick_sort_random(arr, s, left - 1)
    quick_sort_random(arr, left + 1, e)
    return arr

Stability: quick sort is not stable

Quick sort exchanges non-adjacent elements, so an element can jump over an equal element. The lesson's example is [7,3,7,4,5] with pivot 5 (the last index). Tag the 7s as 7_a (index 0) and 7_b (index 2) and watch the partition loop.

4Bucket sort

The last sort in the course. Not as widely used as the others, but important, because it is the one sort that beats O(n log n). It works when the values are within a specific, known range.

The idea: count, then write back

Take an array of size 6 with values in the inclusive range 0-2. Create a "bucket" for each possible value: 0, 1, 2. A bucket here is just a position in a small array that stores the frequency (count) of that value. After counting, overwrite the original array with each value repeated count times, in order.

def bucketSort(arr):
    # Assuming arr only contains 0, 1 or 2
    counts = [0, 0, 0]

    # Count the quantity of each val in arr
    for n in arr:
        counts[n] += 1

    # Fill each bucket in the original array
    i = 0
    for n in range(len(counts)):
        for j in range(counts[n]):
            arr[i] = n
            i += 1
    return arr

• i tracks the next insertion position in arr.
• n tracks the current position in counts, which is also the value being written.
• j tracks how many times counts[n] has been written.

Example: arr = [2,1,2,0,0,2]. Counting gives counts = [2,1,3]: two 0s, one 1, three 2s. Then n=0: the inner loop runs 2 times, writing arr[0] and arr[1] = 0. Continue for each number and the array becomes [0,0,1,2,2,2].

Time: a nested loop that is O(n), not O(n²)

The first loop counts: n steps. The second part has a loop inside a loop, and the reflex is to say O(n²). Look closer. The outer loop runs once per bucket (3 times). The inner loop runs counts[n] times: 2, then 1, then 3. Add them: 2 + 1 + 3 = 6 = n. The total number of writes is exactly n, no matter how the values are distributed, because every element is counted once and written once. So the whole algorithm is O(n) (strictly O(n + k) where k is the number of buckets, and k is a small constant here).

Stability

The counting version overwrites the original array. There is no swapping and no moving of the original elements; the output is built from the counts. So the relative order of equal elements cannot be preserved: the "two 2s" in the output are not the original 2s at all. For plain integers this does not matter, since a 2 is a 2. For records sorted by a key it does, and then you need the stable prefix-sum version of counting sort, which is outside this lesson.

Closing: the course table

Bucket sort is O(n) but only works if the data is within a specified range. The safest general bet is merge sort or quick sort.

5Moves that solve most sorting problems

In an interview you will rarely write merge sort from scratch. You will call Python's sort with the right key, and you will be asked to explain which algorithm you would use and why. This section covers both.

Which sort to say, and why

Move 1: sorted() and list.sort() with key and reverse

Python's built-in sort is Timsort: a hybrid of merge sort and insertion sort. It is stable, O(n log n) worst case, and O(n) on already sorted input (it detects runs). sorted(x) returns a new list and works on any iterable. x.sort() sorts the list in place and returns None, a classic bug source.

a = [3, 1, 2]
b = sorted(a)                 # b = [1, 2, 3], a untouched
a.sort()                      # a is now [1, 2, 3]; a.sort() itself returns None

sorted([3, 1, 2], reverse=True)                      # [3, 2, 1]
sorted(["banana", "fig", "apple", "kiwi"], key=len)  # ['fig', 'kiwi', 'apple', 'banana']
sorted(["peach", "fig", "grape"], key=len)          # ['fig', 'peach', 'grape']  (stable: peach stays before grape)

key is a function called once per element; the sort compares the results, not the elements. Think of it as "sort by this". Stability means elements with equal keys keep their input order.

Move 2: sorting tuples and multi-key sorts

Tuples compare position by position, so returning a tuple from key gives you "sort by A, then by B". To sort one field descending and another ascending, negate the numeric field. This is the whole trick behind Top K Frequent Elements and most "sort by frequency" questions.

from collections import Counter

pairs = [(2, "b"), (1, "z"), (2, "a")]
sorted(pairs)                               # [(1,'z'), (2,'a'), (2,'b')]   whole tuple
sorted(pairs, key=lambda p: p[0])          # [(1,'z'), (2,'b'), (2,'a')]   by number, stable
sorted(pairs, key=lambda p: (-p[0], p[1]))  # [(2,'a'), (2,'b'), (1,'z')]   number desc, letter asc

def sort_by_freq_then_value(nums):
    # most frequent first; ties broken by the smaller value first
    cnt = Counter(nums)
    return sorted(cnt, key=lambda x: (-cnt[x], x))

def top_k_frequent(nums, k):                 # LeetCode 347, the O(n log n) version
    cnt = Counter(nums)
    return sorted(cnt, key=lambda x: -cnt[x])[:k]

def merge_intervals(intervals):              # LeetCode 56: sort by start, then sweep
    intervals.sort(key=lambda iv: iv[0])
    out = []
    for start, end in intervals:
        if out and start <= out[-1][1]:        # overlaps the last kept interval
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

Move 3: a custom comparator with cmp_to_key

Sometimes "which is smaller" cannot be expressed as a key per element; it depends on the pair. Largest Number is the classic: put a before b if the string a + b is bigger than b + a. Python 3 removed the cmp argument, so wrap a two-argument function with functools.cmp_to_key. Return negative for "a first", positive for "b first", 0 for tie.

from functools import cmp_to_key

def largest_number(nums):                    # LeetCode 179
    def compare(a, b):
        if a + b > b + a:
            return -1                       # a should come first
        if a + b < b + a:
            return 1
        return 0
    strs = sorted(map(str, nums), key=cmp_to_key(compare))
    return "0" if strs[0] == "0" else "".join(strs)

largest_number([3, 30, 34, 5, 9])   # "9534330"

Move 4: counting sort when the range is small

Whenever the problem says "values are between 0 and k" and k is small, say the phrase "counting sort, O(n + k)". It is the bucket sort from lesson 13 with the bucket count as a parameter. Sort Colors (values 0, 1, 2) is exactly bucketSort.

def counting_sort(arr, k):
    # values are integers in 0..k inclusive
    counts = [0] * (k + 1)
    for n in arr:
        counts[n] += 1
    i = 0
    for v in range(k + 1):
        for _ in range(counts[v]):
            arr[i] = v
            i += 1
    return arr

counting_sort([4, 1, 3, 1, 0, 4], k=4)   # [0, 1, 1, 3, 4, 4]

6Big-O summary

Say the best, average and worst cases separately. Interviewers listen for the difference between quick sort's average and worst.

• Insertion best case O(n): already sorted input; the inner loop never runs. Worst case: reverse sorted input.
• Merge space O(n): temp arrays (n at any moment) plus the call stack (log n). Summed, not multiplied.
• Quick sort O(log n)* stack: O(log n) when the pivot splits evenly; O(n) in the worst case (sorted input, last-index pivot). Randomizing the pivot makes the worst case unlikely, not impossible.
• Bucket k: the number of possible values. With k = 3 it is a constant and the lesson simply writes O(n). With k = 10⁹ it is useless.

7Mistakes to watch for

8Practice, in this order

Solve without the notes open. For 912, implement merge sort first, then quick sort, then compare the run time on the same input.

Your next step today: LeetCode 912. Write mergeSort and merge from memory, submit, then write quickSort and submit again. If quick sort times out on a test with many equal values, that is the O(n²) case; add the random pivot.

9Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.