Quick Sort Basics — Lomuto/Hoare Mental Models

Quick sort basics focus on one pivot pass: move smaller elements left, larger right, then recurse. Master the partition loop before optimizing.

Why this shows up in the real world

Coding bootcamps still teach Lomuto partition because it fits on a whiteboard. Competitive programmers memorize a compact partition snippet they can type fast under time pressure—basics first, micro-optimizations later.

Core idea (explained for students)

Pick pivot p (often last element in Lomuto). Scan with i boundary of “less region”; for each j, if a[j] <= p, swap a[i] with a[j] and increment i. Finally swap pivot into place between regions. Recurse on [lo, i-1] and [i+1, hi].

Try this in Python

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


nums = [5, 1, 4, 2, 8]
print(lomuto_partition(nums, 0, len(nums) - 1), nums)

Common mistakes

• Pivot ends up not where partition expects—off-by-one.
• Using <= vs < inconsistently with duplicate policy.
• Infinite recursion when all elements equal—use three-way fix.

Key takeaways

• Partition is the heart—drill it.
• Draw states for a 6-element example.
• Compare Lomuto vs Hoare trade-offs.