How to Implement Quicksort from Scratch

Understanding the Basics of Quicksort

Welcome to the world of Divide-and-Conquer! Quicksort is often the default choice for sorting in standard libraries (like C++ STL or Java's dual-pivot Quicksort) because it is incredibly fast in practice. Unlike Merge Sort, which requires extra memory to merge arrays, Quicksort usually sorts in-place, meaning it rearranges the data right where it sits. This makes it a memory-efficient champion for large datasets.

def partition(arr, low, high):
    pivot = arr[high]       # Choose last element
    i = low - 1             # Tracks "smaller than pivot" region

    for j in range(low, high):
        if arr[j] <= pivot: # Found a smaller element?
            i += 1          # Expand smaller region
            swap(arr[i], arr[j]) # Swap to move it left

    swap(arr[i+1], arr[high])   # Place pivot in final spot
    return i + 1                # Return pivot's index

Choosing a Pivot Strategy

Imagine you are using a lever to lift a heavy rock. The pivot is the fulcrum. If you place the fulcrum right in the middle, you get a perfect balance and can lift the weight easily. But if you place the fulcrum right at the very edge, you have to push down much harder.

In Quicksort, the pivot determines how we split the data. A good pivot (close to the middle value) creates balanced recursive calls, leading to O(n log n) speed. A bad pivot (the smallest or largest value) creates unbalanced calls, dragging performance down to O(n²).

def median_of_three(arr, low, high):
    mid = (low + high) // 2
    a, b, c = arr[low], arr[mid], arr[high]
    
    # Find the median value among a, b, c
    if a <= b <= c or c <= b <= a:
        pivot_val = b
        pivot_idx = mid
    elif b <= a <= c or c <= a <= b:
        pivot_val = a
        pivot_idx = low
    else:
        pivot_val = c
        pivot_idx = high
    
    # Swap the chosen median to the 'high' position
    # so we can reuse our standard partition logic
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    
    return arr[high]

Recursive Quicksort Logic

Welcome to the magic of Divide and Conquer! You've learned how to pick a pivot and partition an array. Now, imagine you've just finished a partition. The pivot is locked in its final spot. The left side is messy, and the right side is messy. But here is the beautiful secret: you don't need to sort the whole thing again.

You simply apply the exact same process to the left mess, and then to the right mess. It's like opening a set of Russian nesting dolls. You open one, find two smaller ones inside, and repeat the process until you reach the tiniest doll that cannot be opened. In coding terms, we call this Recursion.

def quicksort(arr, low, high):
    # 1. Base Case: Stop if the subarray is empty or has 1 element
    if low < high:
        
        # 2. Divide: Partition the array
        pivot_idx = partition(arr, low, high)
        
        # 3. Conquer: Recursively sort the two halves
        quicksort(arr, low, pivot_idx - 1)      # Left side
        quicksort(arr, pivot_idx + 1, high)     # Right side

def quicksort_optimized(arr, low, high):
    while low < high:
        pivot_idx = partition(arr, low, high)
        
        # Always recurse on the SMALLER partition
        if (pivot_idx - low) < (high - pivot_idx):
            quicksort_optimized(arr, low, pivot_idx - 1)
            # Loop handles the larger right side:
            low = pivot_idx + 1 
        else:
            quicksort_optimized(arr, pivot_idx + 1, high)
            # Loop handles the larger left side:
            high = pivot_idx - 1

Handling Edge Cases: The Duplicate Element Trap

Imagine you are sorting a deck of cards, but the deck is mostly identical cards. If you use a standard sorting method, you might waste time comparing every single card to every other card, even though they are all the same.

This is the Duplicate Element Trap in Quicksort. If your array looks like [5, 5, 5, 5, 5, 5], a standard partition scheme treats every 5 as "equal" and often pushes them all to one side. This destroys the "Divide-and-Conquer" balance, turning your O(n log n) algorithm into a slow O(n²) disaster.

def quicksort_three_way(arr, low, high):
    if low >= high:
        return
    
    pivot = arr[low]  # Simplified pivot choice
    lt, i, gt = low, low, high
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:  # arr[i] == pivot
            i += 1  # Skip duplicates!
    
    # Recurse only on the smaller and larger parts
    quicksort_three_way(arr, low, lt - 1)
    quicksort_three_way(arr, gt + 1, high)

Time Complexity Analysis: The Work Tree

To truly understand why Quicksort is fast (or slow), we need to look at the Recursion Tree. Imagine every time you make a recursive call, you are adding a new branch to a tree. The speed of the algorithm depends entirely on the shape of this tree.

T(n) = T(k) + T(n - k - 1) + Θ(n)

Space Complexity Analysis: The Hidden Cost of Recursion

You've mastered the speed of Quicksort, but every algorithm has a price. While Quicksort is famous for being in-place (meaning it doesn't need a second array like Merge Sort), it isn't free. The cost lies in the Recursion Stack.

Think of the call stack like a stack of plates. Every time your function calls itself, you place a new plate on top to hold the "current state" (variables like low and high). When the function finishes, you remove the plate. The total memory used is the height of the stack at its deepest point.

def quicksort_optimized(arr, low, high):
    while low < high:
        pivot_idx = partition(arr, low, high)
        
        # Determine which side is smaller
        left_size = pivot_idx - low
        right_size = high - pivot_idx
        
        if left_size < right_size:
            # Recurse on smaller (Left)
            quicksort_optimized(arr, low, pivot_idx - 1)
            # Loop on larger (Right) - reuses current frame!
            low = pivot_idx + 1 
        else:
            # Recurse on smaller (Right)
            quicksort_optimized(arr, pivot_idx + 1, high)
            # Loop on larger (Left) - reuses current frame!
            high = pivot_idx - 1

Variations and Optimizations

You've learned the core mechanics of Quicksort, but in the real world, "textbook" algorithms are often tweaked for performance. One of the most famous optimizations is the Hybrid Approach.

Imagine you are moving a house. Quicksort is the heavy truck used to move the main furniture. But when you need to move a single, delicate vase, you don't bring out the truck—you use your hands.

Similarly, when Quicksort's recursive calls get very small (e.g., fewer than 10 elements), the overhead of function calls and partitioning logic becomes expensive. For these tiny chunks, a simple Insertion Sort is faster. A Hybrid Quicksort detects this and switches tools, saving time and reducing recursion depth.

def insertion_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def quicksort_hybrid(arr, low, high):
    THRESHOLD = 10  # Switch to insertion sort if size <= 10
    
    while low < high:
        # 1. Check Threshold
        if high - low + 1 <= THRESHOLD:
            insertion_sort(arr, low, high)
            return  # Done with this chunk!
        
        # 2. Partition
        pivot_idx = partition(arr, low, high)
        
        # 3. Tail Recursion Optimization
        # Recurse on smaller side, loop on larger side
        if (pivot_idx - low) < (high - pivot_idx):
            quicksort_hybrid(arr, low, pivot_idx - 1)
            low = pivot_idx + 1
        else:
            quicksort_hybrid(arr, pivot_idx + 1, high)
            high = pivot_idx - 1

Advanced: Parallel Quicksort

You have mastered the sequential logic of Quicksort. Now, let's talk about speed. Quicksort's divide-and-conquer structure naturally lends itself to parallel execution.

Imagine you are organizing a massive library. After you split the books into two piles (Left and Right), you don't need to organize both yourself. You can hire a second worker to organize the Right pile while you work on the Left. Since the two piles are independent, you can work simultaneously!

def parallel_quicksort(arr, low, high, depth=0, max_depth=4):
    # 1. Sequential Cutoff: If array is small, just sort it!
    if high - low <= 100:
        sequential_quicksort(arr, low, high)
        return

    pivot_idx = partition(arr, low, high)

    # 2. Parallelism Check: Are we allowed to spawn new workers?
    if depth < max_depth:
        # Spawn two tasks: one for left half, one for right half
        with concurrent.futures.ProcessPoolExecutor() as executor:
            future_left = executor.submit(parallel_quicksort, arr, low, pivot_idx-1, depth+1, max_depth)
            future_right = executor.submit(parallel_quicksort, arr, pivot_idx+1, high, depth+1, max_depth)
            # Wait for both to finish
            concurrent.futures.wait([future_left, future_right])
    else:
        # 3. Depth Limit Reached: Switch back to sequential to save resources
        parallel_quicksort(arr, low, pivot_idx-1, depth+1, max_depth)
        parallel_quicksort(arr, pivot_idx+1, high, depth+1, max_depth)

Frequently Asked Questions (FAQ)

Hello! I'm Professor Pixel. You've reached the troubleshooting corner. Here, we answer the most common questions students ask when they first encounter Quicksort. These aren't just theoretical questions—they are the exact bugs you might face in your code.

def quicksort(arr, low, high):
    if low >= high:  # Stop here!
        return
    # ... rest of logic