⚡ Quick Sort

Intermediate ~15 min read

You're organizing a library. Instead of comparing every book with every other book, you have a smarter strategy: Pick a reference book (the "pivot"), put smaller books on the left, larger books on the right. The pivot? It's already in its final spot! That's the power of Quick Sort!

The Smart Organizer

Imagine sorting mail into "before M" and "after M" piles based on a reference letter:

The Strategy

Pick a pivot: Choose a reference element (e.g., last element)
Partition: Move smaller elements left, larger elements right
Pivot is sorted! It's now in its final position
Recurse: Repeat for left and right subarrays

Key insight: Each partition puts ONE element in its final sorted position!

How Quick Sort Works

The Algorithm

If array has ≤ 1 element → already sorted! (base case)
Choose a pivot (commonly last element)
Partition: rearrange so smaller elements are left, larger are right
Pivot is now in its final sorted position!
Recursively sort left subarray
Recursively sort right subarray

See It in Action

Watch how Quick Sort picks a pivot, partitions around it, and recursively sorts:

Understanding the Process

🟡 Yellow (Pivot): Selected pivot element
🟣 Purple (Comparing): Element being compared with pivot
🟠 Orange (Swapping): Elements being swapped
🟢 Green (Sorted): Pivot in final position
Each partition: O(n) work
Average depth: log n levels
Total: O(n) × O(log n) = O(n log n) average

The Code

"""
Quick Sort - Basic Implementation
The Smart Organizer: Pick a pivot, partition, recurse!
"""

def quick_sort(arr):
    """
    Quick Sort: Divide and conquer with smart partitioning
    Time: O(n log n) average, O(n²) worst
    Space: O(log n) for recursion stack
    """
    print(f"Sorting: {arr}")
    quick_sort_helper(arr, 0, len(arr) - 1)
    return arr

def quick_sort_helper(arr, low, high):
    """Recursive helper function"""
    if low < high:
        # Partition the array and get pivot index
        pivot_index = partition(arr, low, high)
        
        print(f"Pivot {arr[pivot_index]} is in final position {pivot_index}")
        print(f"Array: {arr}")
        
        # Recursively sort left and right subarrays
        quick_sort_helper(arr, low, pivot_index - 1)
        quick_sort_helper(arr, pivot_index + 1, high)

def partition(arr, low, high):
    """
    Lomuto Partition Scheme
    - Choose last element as pivot
    - Partition array around pivot
    - Return pivot's final position
    """
    pivot = arr[high]  # Choose last element as pivot
    print(f"\n--- Partitioning [{low}:{high}] with pivot {pivot} ---")
    
    i = low - 1  # Index of smaller element
    
    for j in range(low, high):
        # If current element is smaller than pivot
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
            print(f"Swap: {arr[j]} ↔ {arr[i]} → {arr}")
    
    # Place pivot in correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    print(f"Pivot {pivot} placed at index {i + 1}")
    
    return i + 1

# Example 1: Basic sorting
print("=" * 50)
print("Example 1: Basic Quick Sort")
print("=" * 50)
arr1 = [38, 27, 43, 3, 9, 82, 10]
print(f"Original: {arr1}")
result1 = quick_sort(arr1.copy())
print(f"\nSorted: {result1}\n")

# Example 2: Already sorted (worst case!)
print("=" * 50)
print("Example 2: Already Sorted (Worst Case!)")
print("=" * 50)
arr2 = [1, 2, 3, 4, 5]
print(f"Original: {arr2}")
print("Notice: Each partition only reduces size by 1!")
result2 = quick_sort(arr2.copy())
print(f"\nSorted: {result2}\n")

# Example 3: Reverse sorted
print("=" * 50)
print("Example 3: Reverse Sorted")
print("=" * 50)
arr3 = [5, 4, 3, 2, 1]
print(f"Original: {arr3}")
result3 = quick_sort(arr3.copy())
print(f"\nSorted: {result3}\n")

# Example 4: Duplicates
print("=" * 50)
print("Example 4: With Duplicates")
print("=" * 50)
arr4 = [3, 7, 3, 1, 7, 3]
print(f"Original: {arr4}")
result4 = quick_sort(arr4.copy())
print(f"\nSorted: {result4}\n")

print("=" * 50)
print("Key Insights:")
print("=" * 50)
print("✓ Each partition puts ONE element in final position")
print("✓ Pivot choice matters! (last element can be bad)")
print("✓ Already sorted = worst case O(n²)")
print("✓ Random data = average case O(n log n)")
print("✓ In-place sorting (no extra array needed)")

Output

Click Run to execute your code

The Partition Function: This is where the magic happens! We rearrange elements so that everything smaller than the pivot goes left, everything larger goes right. The pivot ends up in its final sorted position!

Quick Quiz

Why does each partition put the pivot in its final position?

Show answer
After partitioning, all elements to the left of the pivot are smaller, and all elements to the right are larger. This means the pivot is exactly where it belongs in the sorted array! No matter how we sort the left and right subarrays, the pivot won't move.
What happens if we always pick the smallest element as pivot?

Show answer
Disaster! We'd partition into [nothing] and [everything else]. That's n levels of O(n) work = O(n²). This is why pivot selection matters! Always picking the first or last element can be bad if the data is already sorted.

Pivot Selection Strategies

The pivot choice can make or break Quick Sort's performance:

"""
Quick Sort - Different Pivot Strategies
Comparing: First, Last, Middle, Random, Median-of-Three
"""

import random
import time

def quick_sort_last_pivot(arr, low, high):
    """Strategy 1: Last element as pivot (Lomuto)"""
    if low < high:
        pivot_index = partition_last(arr, low, high)
        quick_sort_last_pivot(arr, low, pivot_index - 1)
        quick_sort_last_pivot(arr, pivot_index + 1, high)

def partition_last(arr, low, high):
    """Lomuto partition: last element as pivot"""
    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

def quick_sort_middle_pivot(arr, low, high):
    """Strategy 2: Middle element as pivot"""
    if low < high:
        pivot_index = partition_middle(arr, low, high)
        quick_sort_middle_pivot(arr, low, pivot_index - 1)
        quick_sort_middle_pivot(arr, pivot_index + 1, high)

def partition_middle(arr, low, high):
    """Middle element as pivot"""
    mid = (low + high) // 2
    # Move middle to end for standard partition
    arr[mid], arr[high] = arr[high], arr[mid]
    return partition_last(arr, low, high)

def quick_sort_random_pivot(arr, low, high):
    """Strategy 3: Random element as pivot"""
    if low < high:
        pivot_index = partition_random(arr, low, high)
        quick_sort_random_pivot(arr, low, pivot_index - 1)
        quick_sort_random_pivot(arr, pivot_index + 1, high)

def partition_random(arr, low, high):
    """Random element as pivot"""
    rand_index = random.randint(low, high)
    # Move random to end for standard partition
    arr[rand_index], arr[high] = arr[high], arr[rand_index]
    return partition_last(arr, low, high)

def quick_sort_median_of_three(arr, low, high):
    """Strategy 4: Median of first, middle, last"""
    if low < high:
        pivot_index = partition_median_of_three(arr, low, high)
        quick_sort_median_of_three(arr, low, pivot_index - 1)
        quick_sort_median_of_three(arr, pivot_index + 1, high)

def partition_median_of_three(arr, low, high):
    """Median of three as pivot"""
    mid = (low + high) // 2
    
    # Find median of arr[low], arr[mid], arr[high]
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[mid] > arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
    
    # Now arr[mid] is the median, move it to end
    arr[mid], arr[high] = arr[high], arr[mid]
    return partition_last(arr, low, high)

# Test different strategies
def test_strategy(name, sort_func, arr):
    """Test a pivot strategy"""
    test_arr = arr.copy()
    start = time.perf_counter()
    sort_func(test_arr, 0, len(test_arr) - 1)
    end = time.perf_counter()
    return (end - start) * 1000  # Convert to ms

print("=" * 70)
print("Quick Sort Pivot Strategies Comparison")
print("=" * 70)

# Test Case 1: Random data (best for all strategies)
print("\n📊 Test 1: Random Data (n=1000)")
print("-" * 70)
random_data = [random.randint(1, 1000) for _ in range(1000)]

strategies = [
    ("Last Element", quick_sort_last_pivot),
    ("Middle Element", quick_sort_middle_pivot),
    ("Random Element", quick_sort_random_pivot),
    ("Median-of-Three", quick_sort_median_of_three)
]

for name, func in strategies:
    time_ms = test_strategy(name, func, random_data)
    print(f"{name:20} → {time_ms:6.2f}ms")

# Test Case 2: Already sorted (worst for last pivot!)
print("\n📊 Test 2: Already Sorted (n=500) - Worst Case for Last Pivot!")
print("-" * 70)
sorted_data = list(range(500))

for name, func in strategies:
    time_ms = test_strategy(name, func, sorted_data)
    print(f"{name:20} → {time_ms:6.2f}ms")

# Test Case 3: Reverse sorted
print("\n📊 Test 3: Reverse Sorted (n=500)")
print("-" * 70)
reverse_data = list(range(500, 0, -1))

for name, func in strategies:
    time_ms = test_strategy(name, func, reverse_data)
    print(f"{name:20} → {time_ms:6.2f}ms")

# Test Case 4: Many duplicates
print("\n📊 Test 4: Many Duplicates (n=1000)")
print("-" * 70)
duplicate_data = [random.randint(1, 10) for _ in range(1000)]

for name, func in strategies:
    time_ms = test_strategy(name, func, duplicate_data)
    print(f"{name:20} → {time_ms:6.2f}ms")

print("\n" + "=" * 70)
print("Key Insights:")
print("=" * 70)
print("✓ Last Pivot: Simple but TERRIBLE on sorted data (O(n²))")
print("✓ Middle Pivot: Better than last, still can be bad")
print("✓ Random Pivot: Good average case, prevents worst case")
print("✓ Median-of-Three: Best overall, used in practice")
print("\n💡 Real libraries use Median-of-Three or Random!")
print("💡 C++ std::sort uses Intro Sort (Quick + Heap)")

Output

Click Run to execute your code

Strategy	Pros	Cons	Use When
Last Element	Simple, fast	O(n²) on sorted data!	Random data only
Middle Element	Better than last	Still can be bad	Unknown data
Random Element	Prevents worst case	Randomness overhead	Adversarial data
Median-of-Three	Best overall	Slightly more complex	Production use!

Why O(n log n) Average?

Let's break down the complexity:

Case	Time	Why
Best	O(n log n)	Pivot always splits evenly
Average	O(n log n)	Most pivots are reasonably good
Worst	O(n²)	Pivot always smallest/largest (sorted data!)
Space	O(log n)	Recursion stack depth

⚠️ The Worst Case

Unlike Merge Sort, Quick Sort can degrade to O(n²)!

When: Already sorted data with bad pivot choice
Why: Each partition only reduces size by 1
Solution: Use median-of-three or random pivot

Quick Sort vs Merge Sort

The big question: Which is better?

Feature	Merge Sort	Quick Sort
Strategy	"Split evenly, merge carefully"	"Pick pivot, partition smartly"
Best Case	O(n log n)	O(n log n)
Average Case	O(n log n)	O(n log n)
Worst Case	O(n log n) ✓	O(n²) ⚠️
Space	O(n) - needs extra array	O(log n) - recursion only ✓
Stable	Yes ✓	No
In-Place	No	Yes ✓
Cache Performance	Good	Excellent ✓
In Practice	"Steady and predictable"	"Usually faster!" ✓

The Verdict

Quick Sort wins in practice! Here's why:

✓ Better cache locality (works on nearby elements)
✓ In-place (no extra memory needed)
✓ Smaller constant factors
✓ With good pivot selection, worst case is rare

But Merge Sort wins when:

✓ You need guaranteed O(n log n)
✓ You need stability
✓ Data might be adversarial

When to Use Quick Sort

✅ Use When:

Need speed: Fastest in practice for random data
Limited memory: In-place with O(log n) space
Cache matters: Excellent cache performance
Random data: Average case is very likely
Can choose pivot: Median-of-three available

❌ Avoid When:

Need guaranteed performance: Can be O(n²)
Need stability: Quick Sort is unstable
Data might be sorted: Worst case likely
Adversarial input: Someone might exploit worst case

🎯 Real-World Use

Quick Sort is everywhere!

C++ std::sort(): Uses Intro Sort (Quick + Heap)
Unix sort: Quick Sort variant
Java Arrays.sort(): Dual-pivot Quick Sort for primitives
Databases: In-memory sorting

Common Misconceptions

❌ Misconception 1: "Quick Sort is always O(n log n)"

Reality: It's O(n²) in the worst case!

Worst case: Already sorted data with bad pivot
Example: [1,2,3,4,5] with last element as pivot
Each partition: Only reduces size by 1
Total: n levels × O(n) work = O(n²)

Solution: Use median-of-three or random pivot!

❌ Misconception 2: "Quick Sort is always faster than Merge Sort"

Reality: It depends on the data and implementation!

Random data: Quick Sort usually wins
Sorted data: Merge Sort wins (if bad pivot)
Small arrays: Insertion Sort wins!
Linked lists: Merge Sort wins (no random access)

Best choice: Depends on your specific use case!

❌ Misconception 3: "Quick Sort uses no extra space"

Reality: Recursion uses O(log n) stack space!

Recursion depth: log n on average
Each call: Stores local variables on stack
Worst case: O(n) stack space (unbalanced)
Still better: Than Merge Sort's O(n) array

Note: Can be made iterative with explicit stack!

❌ Misconception 4: "Pivot selection doesn't matter much"

Reality: It's the difference between O(n log n) and O(n²)!

Bad pivot: Always smallest/largest → O(n²)
Good pivot: Near median → O(n log n)
Last element: Terrible on sorted data
Median-of-three: Almost always good

Real libraries: Use sophisticated pivot selection!

💡 Key Takeaway

Quick Sort is fast in practice but not guaranteed:

✅ Average case: O(n log n) - usually very fast
✅ In-place: O(log n) space
✅ Cache-friendly: Works on nearby elements
⚠️ Worst case: O(n²) - rare with good pivot
⚠️ Unstable: Equal elements may swap

Understanding Quick Sort teaches you about trade-offs, pivot selection, and why "average case" matters!

Summary

The 3-Point Quick Sort Guide

Strategy: Pick pivot, partition, recurse - each partition sorts ONE element
Complexity: O(n log n) average, O(n²) worst - pivot choice matters!
Trade-off: Speed and space efficiency vs guaranteed performance

Interview tip: Mention Quick Sort for in-place sorting with good average performance. Explain partition process and why pivot selection matters. Compare with Merge Sort!

What's Next?

You've completed Module 3: Sorting Algorithms! You now understand O(n²) sorts (Bubble, Selection, Insertion) and O(n log n) sorts (Merge, Quick). Next: Searching Algorithms and advanced data structures!

Practice: Implement Quick Sort with different pivot strategies. Try the three-way partition for arrays with many duplicates!

Previous Merge Sort

Next Heap Sort