Quick Sort is one of those algorithms that sounds simple in a textbook—"pick a pivot, partition the array, repeat"—but the moment you start typing C code, you'll likely find yourself staring at a segmentation fault or a loop that never ends. It's all about the index bookkeeping.

How do I actually implement the partition logic?

The partition step is where the real work happens. Your goal is to pick a "pivot" element and rearrange the array so that everything smaller than the pivot is on the left and everything larger is on the right. I usually recommend the Lomuto partition scheme when you're starting out because it's easier to reason about than Hoare's.

Imagine we're sorting a set of network latency measurements in milliseconds. If our pivot is 50ms, we want to shuffle the array so 50ms ends up in its final, sorted position.

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Picking the last element as pivot
    int i = (low - 1);    // Index of the smaller element

    for (int j = low; j < high; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++; 
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // Swap the pivot element to its correct position
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return (i + 1);
}

Notice that i tracks the "boundary" of the elements known to be smaller than the pivot. Every time we find a small element, we grow that boundary and swap the element into it. It's a bit like pushing all the "small" numbers to the front of the line.

Does it really matter which element I pick as the pivot?

In a perfect world, no. In the real world, absolutely. If you always pick the last element and your input array is already sorted (or sorted in reverse), Quick Sort collapses from a snappy O(n log n) to a sluggish O(n²). You basically turn your efficient divide-and-conquer algorithm into a very expensive version of Bubble Sort.

I've seen production systems crawl because someone used a naive pivot on pre-sorted telemetry data. To fix this, you can pick a random index as the pivot or use the "median-of-three" rule (picking the median of the first, middle, and last elements). For the sake of this lesson, we'll stick to the last element for simplicity, but keep this in the back of your mind for when you're writing production-grade libraries.

How do I put the recursive calls together without blowing the stack?

The recursive part is actually the cleanest bit of the code. Once partition() tells you where the pivot landed, that index is "locked." You don't ever need to touch it again. You just tell the function to do the exact same thing to the slice of the array to the left of the pivot, and then to the slice on the right.

The key is the base case. If you forget if (low < high), your program will recurse infinitely until the stack overflows. Here is how the orchestration looks:

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);

        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

It's an elegant loop of "partition, then split." You're essentially narrowing the window of unsorted data until the windows are only one element wide, at which point the entire array is sorted by definition.

📋 Practical Task

Exercise: Implementing a Randomized Pivot for Latency Data

Using the quickSort and partition logic from this lesson, modify the implementation to prevent the O(n²) worst-case scenario. Create a program that sorts an array of 100 integers representing network latency (values between 1ms and 1000ms).

• Implement a function swap(int* a, int* b) to handle element exchanges.
• Modify the partition function or create a wrapper that selects a random index between low and high, swaps that random element with the element at high, and then proceeds with the standard Lomuto partition.
• Test your implementation with an array that is already sorted to verify that your randomized pivot prevents the performance collapse.
• Print the array before and after sorting to the console.