Offensive Security Researcher & Quantum Cryptography Analyst

Quick Sort Algorithm: Working, Explanation, and Efficient Sorting Technique

Abdul Wahab Junaid
quick sort algorithm and working of this algorithm

quick sort algorithm and working of this algorithm

I consider quick sort one of the most practically important sorting algorithms I have ever worked with. It is a comparison-based, divide-and-conquer algorithm that sorts an array by picking a “pivot” element and partitioning the rest of the data around it. What draws me to quick sort is how it manages to be both conceptually elegant and, in most real-world cases, faster than many of its O(n log n) competitors because of its excellent cache behavior and in-place operation. It is the default sort in many standard libraries (often in a hybrid form), which tells me how much trust the software engineering community places in it.

History and Background

Quick sort was developed by Tony Hoare in 1959 while he was working as a visiting student in Moscow, trying to solve a machine translation problem that required sorting words. He published the algorithm in 1961 in The Computer Journal, and it quickly became one of the most studied and used sorting algorithms in computer science. Hoare’s original partitioning scheme is still taught today, though many practical implementations now use the simpler Lomuto partition scheme popularized later, or hybrid approaches like Introsort (introduced by David Musser in 1997), which switches to heap sort when recursion gets too deep to guard against quick sort’s worst case.

Problem Statement

I need an efficient, general-purpose, in-place sorting method that performs well on average across a wide range of real-world data without needing extra memory proportional to the input size. Quick sort addresses this by recursively partitioning data around pivot values, aiming for average-case O(n log n) performance while using only O(log n) additional space for recursion, unlike merge sort which needs O(n) extra space.

Core Concepts

How It Works

I approach quick sort in three repeating stages:

  1. I choose a pivot element from the current subarray.
  2. I partition the subarray so that everything smaller than the pivot ends up to its left, and everything larger ends up to its right — after this step, the pivot sits in its final sorted position.
  3. I recursively apply the same process to the left and right subarrays (excluding the pivot), continuing until each subarray has zero or one element, which is trivially sorted.

Working Principle

The core insight I rely on is that partitioning does most of the sorting work implicitly. Once I place the pivot correctly relative to every other element, I never need to compare across that boundary again — everything to the left is guaranteed smaller, everything to the right is guaranteed larger. This lets me recurse independently on each half, and because the partitioning step touches every element exactly once per level of recursion, the total work stays efficient as long as the partitions stay reasonably balanced. The algorithm’s real-world speed comes from this in-place, cache-friendly partitioning combined with low constant-factor overhead compared to other O(n log n) sorts.

Mathematical Foundation

If my partitioning always splits the array into two equal halves, the recurrence for quick sort’s running time is:

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$$

By the Master Theorem, this recurrence resolves to:

$$T(n) = O(n \log n)$$

However, in the worst case — where the pivot is always the smallest or largest element (as happens with already-sorted input and a naive pivot choice) — the recurrence becomes:

$$T(n) = T(n-1) + O(n)$$

which resolves to:

$$T(n) = O(n^2)$$

The expected running time, averaged over all possible pivot choices with randomization, can be shown to be $O(n \log n)$ using the linearity of expectation over the number of comparisons made between each pair of elements.

Diagrams

flowchart TD
    A[Start: Unsorted array] --> B[Choose pivot element]
    B --> C[Partition array around pivot]
    C --> D[Elements less than pivot on left]
    C --> E[Elements greater than pivot on right]
    D --> F[Recursively quick sort left subarray]
    E --> G[Recursively quick sort right subarray]
    F --> H[Combine: array is now sorted]
    G --> H

Pseudocode

QUICKSORT(A, low, high)
    if low

Step-by-Step Example

I will sort [7, 2, 1, 6, 8, 5, 3, 4] using the Lomuto partition scheme with the last element as the pivot.

First call: low=0, high=7, pivot = 4 (A[7]) I scan j from 0 to 6, comparing each element with 4:

After the loop, swap A[i+1]=A[3] with A[high]=A[7]: → [2,1,3,4,8,5,7,6]

Pivot 4 is now at index 3, correctly placed. I recurse on the left subarray [2,1,3] (indices 0–2) and the right subarray [8,5,7,6] (indices 4–7), continuing this process until every subarray is fully sorted.

Final sorted output: [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity

Space Complexity

Quick sort is in-place, needing only O(log n) additional space on average for the recursion call stack when partitions are balanced. In the worst case, unbalanced recursion can push this to O(n) stack depth, which is why many practical implementations recurse on the smaller partition first and loop on the larger one (tail-call optimization) to bound stack usage to O(log n) even in adversarial cases.

Correctness Analysis

I can prove quick sort correct through induction on the size of the subarray. The base case is trivial: a subarray of size 0 or 1 is already sorted. For the inductive step, I assume that quick sort correctly sorts any subarray smaller than n. The partition step guarantees that after it finishes, the pivot is in its final, correct sorted position, with every element to its left less than or equal to it and every element to its right greater than or equal to it. Since the left and right subarrays are strictly smaller than n, by the inductive hypothesis they get sorted correctly by the recursive calls, and because the pivot’s position never needs to change again, the whole array ends up sorted.

Advantages

Disadvantages

Applications

Implementation in C

#include stdio.h>

// Swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Lomuto partition scheme: places pivot in correct position
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // choose last element as pivot
    int i = low - 1;        // index of smaller element boundary

    for (int j = low; j  high; j++) {
        if (arr[j]  pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;  // final pivot index
}

// Recursive quick sort function
void quickSort(int arr[], int low, int high) {
    if (low  high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);   // sort left part
        quickSort(arr, pivotIndex + 1, high);  // sort right part
    }
}

int main() {
    int arr[] = {7, 2, 1, 6, 8, 5, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i  n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Sample Input and Output

Input: [7, 2, 1, 6, 8, 5, 3, 4]

Output: Sorted array: 1 2 3 4 5 6 7 8

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version