Quick Sort as Divide and Conquer in DSA C

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorts each part, and then combines them to get a sorted list.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, putting smaller cards on one side and bigger cards on the other, then sorting each side the same way until all cards are in order.

Array before sorting:
[ 8, 3, 7, 6, 2 ]

Pivot chosen (e.g., last element): 2
Partition step divides array into:
[ 2 ] [ 3, 7, 6, 8 ]

Then recursively sort each part.

Dry Run Walkthrough

Input: array: [8, 3, 7, 6, 2]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element (2), partition array around pivot

[2] [3, 7, 6, 8]

Why: Pivot divides array into elements less or equal and greater than pivot

Step 2: Recursively quick sort left part [2] (single element)

[2]

Why: Single element is already sorted

Step 3: Recursively quick sort right part [3, 7, 6, 8], choose pivot 8

[3, 7, 6] [8]

Why: Pivot 8 partitions right part into smaller and equal elements

Step 4: Recursively quick sort [3, 7, 6], choose pivot 6

[3, 6] [7]

Why: Pivot 6 partitions into smaller and greater elements

Step 5: Recursively quick sort [3, 6], choose pivot 6

[3] [6]

Why: Pivot 6 partitions into smaller and equal elements

Step 6: Recursively quick sort [3] (single element)

[3]

Why: Single element is sorted

Step 7: Combine all sorted parts to get final sorted array

[2, 3, 6, 7, 8]

Why: All parts sorted and combined form the fully sorted array

Result:

[2, 3, 6, 7, 8]

Annotated Code

DSA C

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // choose pivot as last element
    int i = low - 1; // index of smaller element
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]); // move smaller element to left
        }
    }
    swap(&arr[i + 1], &arr[high]); // place pivot in correct position
    return i + 1; // return pivot index
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // partition array
        quickSort(arr, low, pi - 1); // sort left part
        quickSort(arr, pi + 1, high); // sort right part
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(", ");
    }
    printf("\n");
}

int main() {
    int arr[] = {8, 3, 7, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printArray(arr, n);
    return 0;
}

int pivot = arr[high]; // choose pivot as last element

select pivot to divide array

if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); }

move elements smaller or equal to pivot to left side

swap(&arr[i + 1], &arr[high]); return i + 1;

place pivot in correct sorted position

if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }

recursively sort left and right parts around pivot

Output

2, 3, 6, 7, 8

Complexity Analysis

Time: O(n log n) average case because the array is divided roughly in half each time and each element is compared once per level

Space: O(log n) due to recursive call stack in average case

vs Alternative: Better than simple sorting like bubble sort O(n^2) because it divides problem into smaller parts instead of comparing all pairs

Edge Cases

empty array

function returns immediately without changes

DSA C

if (low < high) {

array with one element

already sorted, no recursive calls happen

DSA C

if (low < high) {

array with all equal elements

partition keeps elements in place, recursion still works correctly

DSA C

if (arr[j] <= pivot) {

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently by splitting into smaller parts, reach for Quick Sort because it uses divide and conquer to sort fast.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping elements properly during partition
Fix: Always pick pivot as last element and swap elements smaller than pivot to left side, then place pivot correctly

Mistake: Not handling base case when low >= high causing infinite recursion
Fix: Add condition if (low < high) before recursive calls

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting each part recursively.

Use Quick Sort when you want an efficient average-case sorting algorithm with divide and conquer.

The key insight is choosing a pivot to split the array and sorting smaller parts independently.