Quicksort Algorithm — Lomuto vs Hoare, With Code in C, C++, Java, Python and C#

Quicksort’s reputation is that it runs in O(n log n). Its reputation is only half the story: on an already-sorted array with a last-element pivot, the same algorithm makes exactly n(n−1)/2 comparisons and recurses one level per element. Measured on 5,000 sorted values, that is 12,497,500 comparisons and a recursion depth of 5,000 — and at 200,000 elements it segfaults.

This guide covers what separates a quicksort that works from one that collapses: the two partition schemes and why they differ, pivot selection, the worst case demonstrated rather than described, and the recursion fix that prevents the stack overflow. Complete implementations follow in C, C++, Java, Python and C#.

Every program below was compiled and run for this article on Ubuntu 24.04 — GCC 13.3 (-std=c11 and -std=c17), g++ 13.3 (-std=c++17), OpenJDK 21, Python 3.12, and Mono C# 6.8 — all with warnings enabled. All five sort the same array and print the same result. Comparison counts, swap counts, recursion depths and the segfault are captured from instrumented runs, not estimated.

Table of Contents

• What Is the Quicksort Algorithm?
• How Quicksort Works
• Worked Example
• Lomuto vs Hoare: The Two Partition Schemes
• Choosing a Pivot: Where Quicksort Goes Wrong
• The Recursion Depth Problem
• Complexity
• Implementations
• Use the Library Sort in Production
• Key Takeaways
• Frequently Asked Questions
• Conclusion

What Is the Quicksort Algorithm?

Quicksort is a divide-and-conquer sorting algorithm that picks one element as a pivot, rearranges the array so everything smaller sits on one side of the pivot and everything larger on the other, then sorts the two sides recursively. That rearrangement step is called partitioning, and it is where the entire algorithm lives — the recursion is trivial by comparison. Quicksort sorts in place, needing only stack space, and runs in O(n log n) on average but O(n²) in the worst case.

It was published by C. A. R. Hoare in 1961, and the paper is worth knowing about because the algorithm most tutorials teach is not the one Hoare described — see the partition section below.

Hoare, C. A. R. (1962). “Quicksort.” The Computer Journal, Vol. 5, No. 1, pp. 10–16. doi:10.1093/comjnl/5.1.10

How Quicksort Works

1. Choose a pivot from the array.
2. Partition: rearrange so that elements less than the pivot come before it and elements greater come after.
3. Recurse on the sub-array left of the pivot and the sub-array right of it.
4. Stop when a sub-array has fewer than two elements — it is already sorted.

The base case is what makes it terminate; the pivot choice is what makes it fast or slow.

Worked Example

Using the array in every code sample below, with Lomuto partitioning and the last element as pivot:

original:  29 10 14 37 13  5 41 22

First partition, pivot = 22. Everything smaller moves left:

The pivot is now at index 4 and will never move again. Quicksort then repeats on 10 14 13 5 and on 37 41 29. Final result:

5 10 13 14 22 29 37 41

Lomuto vs Hoare: The Two Partition Schemes

Almost every textbook teaches Lomuto, because it is easier to write. Hoare’s original scheme is harder to get right and does substantially less work.

Lomuto uses a single index scanning forward, with the pivot at the end. It maintains a boundary between “known smaller than pivot” and “known not smaller”, swapping each smaller element across it. It returns the pivot’s final index, so the recursive calls exclude it: (lo, p-1) and (p+1, hi).

Hoare uses two indices moving toward each other from both ends, swapping pairs that are on the wrong side. It returns a split point, not a pivot index — the pivot is not necessarily at that position and may not be in its final place at all. The recursive calls are therefore (lo, p) and (p+1, hi), with p included on the left.

That difference is the single most common source of broken quicksort implementations: using Hoare’s partition with Lomuto’s recursive calls produces an infinite loop or a wrong result.

Measured on the same 5,000 random integers:

Hoare performs 2.9× fewer swaps. That is the reason production implementations descend from Hoare’s scheme rather than Lomuto’s — on data where a swap costs more than a comparison, which is most real data, the difference compounds. (The comparison count above is inflated slightly by how the do-while loops are instrumented; the swap ratio is the meaningful figure.)

Choosing a Pivot: Where Quicksort Goes Wrong

The pivot choice determines whether you get O(n log n) or O(n²).

Sorted input is the trap. Picking the last element as pivot means every partition splits the array into one empty side and one side of n−1 elements — the recursion never halves anything. Measured on 5,000 already-sorted values:

Lomuto (last pivot): 12497500 comparisons, recursion depth 5000
   n(n-1)/2 would be 12497500  -> this IS the O(n^2) case
Hoare (middle pivot): 66807 comparisons
   about n log2(n) = 56500

12.5 million comparisons versus 67 thousand — a 187× difference, on identical data, from the pivot choice alone. And note that the measured figure matches n(n−1)/2 exactly, which is what confirms the degenerate behaviour rather than merely suggesting it.

Sorted or nearly-sorted input is not an edge case. It is one of the most common shapes real data arrives in.

Median-of-three, done correctly

Median-of-three sorts the first, middle and last elements, then uses the median as pivot. The step people get wrong is the last one: after finding the median you must move it to wherever your partition function expects to find the pivot. If your partition reads a[hi], the median must end up at hi:

static int median_of_three_partition(int a[], int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[lo])  swap(&a[mid], &a[lo]);
    if (a[hi]  < a[lo])  swap(&a[hi],  &a[lo]);
    if (a[hi]  < a[mid]) swap(&a[hi],  &a[mid]);
    swap(&a[mid], &a[hi]);        /* median now at hi, where Lomuto reads it */
    return lomuto_partition(a, lo, hi);
}

Move it to the wrong index and the sort still produces correct output — it just silently ignores all the work. Measured on 5,000 sorted values, a median-of-three that leaves the median at hi-1 while the partition reads hi does 2.3× more comparisons than one that places it correctly. The bug is invisible in the output and visible only in the runtime.

The Recursion Depth Problem

Quicksort’s O(log n) space claim assumes balanced partitions. When they are unbalanced, recursion depth grows to O(n) — and stack frames are a finite resource:

n=200000, sorted input, naive recursion:
Segmentation fault
  -> exit 139 (segmentation fault: stack exhausted)

That is a real crash from a real run, not a hypothetical. The fix is to recurse into the smaller side and loop on the larger, which bounds the stack at O(log n) regardless of how badly the partitions split:

static void quicksort_safe(int a[], int lo, int hi) {
    while (lo < hi) {
        int p = lomuto_partition(a, lo, hi);
        if (p - lo < hi - p) {          /* recurse into the smaller side */
            quicksort_safe(a, lo, p - 1);
            lo = p + 1;                 /* loop on the larger */
        } else {
            quicksort_safe(a, p + 1, hi);
            hi = p - 1;
        }
    }
}

Same input, same 200,000 sorted elements:

n=200000, sorted input, recurse-smaller-side:
safe : survived

Complexity

Quicksort is not stable: equal elements can be reordered. When stability matters, use merge sort or your language’s library sort, most of which are stable by contract.

Implementations

All five sort the same array and print the same result. Each shows both partition schemes.

C

/* Quicksort in C (C11) - Lomuto and Hoare partition schemes.
 * Compile: gcc -std=c11 -Wall -Wextra -O2 quicksort.c -o quicksort */
#include <stdio.h>
#include <stdlib.h>

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

/* ---- Lomuto partition: pivot is the last element ---- */
static int lomuto_partition(int a[], int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;                       /* boundary of the "smaller" region */
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot)
            swap(&a[++i], &a[j]);
    swap(&a[i + 1], &a[hi]);              /* put the pivot in its final place */
    return i + 1;                         /* pivot index */
}

void quicksort_lomuto(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = lomuto_partition(a, lo, hi);
        quicksort_lomuto(a, lo, p - 1);
        quicksort_lomuto(a, p + 1, hi);
    }
}

/* ---- Hoare partition: two pointers moving inward ---- */
static int hoare_partition(int a[], int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2];    /* middle element, avoids overflow */
    int i = lo - 1, j = hi + 1;
    for (;;) {
        do { i++; } while (a[i] < pivot);
        do { j--; } while (a[j] > pivot);
        if (i >= j) return j;             /* a split point, NOT a pivot index */
        swap(&a[i], &a[j]);
    }
}

void quicksort_hoare(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = hoare_partition(a, lo, hi);
        quicksort_hoare(a, lo, p);        /* p is included on the left */
        quicksort_hoare(a, p + 1, hi);
    }
}

static void print_array(const char *label, const int a[], int n) {
    printf("%-18s", label);
    for (int i = 0; i < n; i++) printf("%3d", a[i]);
    printf("\n");
}

int main(void) {
    int data[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int n = (int)(sizeof data / sizeof data[0]);

    int a[8], b[8];
    for (int i = 0; i < n; i++) a[i] = b[i] = data[i];

    print_array("original:", data, n);
    quicksort_lomuto(a, 0, n - 1);   print_array("Lomuto:", a, n);
    quicksort_hoare(b, 0, n - 1);    print_array("Hoare:", b, n);
    return 0;
}

original:          29 10 14 37 13  5 41 22
Lomuto:             5 10 13 14 22 29 37 41
Hoare:              5 10 13 14 22 29 37 41

C++

// Quicksort in modern C++ (C++17)
// Compile: g++ -std=c++17 -Wall -Wextra -O2 quicksort.cpp -o quicksort
#include <algorithm>
#include <iostream>
#include <vector>

int lomutoPartition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j)
        if (a[j] < pivot)
            std::swap(a[++i], a[j]);
    std::swap(a[i + 1], a[hi]);
    return i + 1;
}

void quicksortLomuto(std::vector<int>& a, int lo, int hi) {
    if (lo < hi) {
        int p = lomutoPartition(a, lo, hi);
        quicksortLomuto(a, lo, p - 1);
        quicksortLomuto(a, p + 1, hi);
    }
}

int hoarePartition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2];
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { ++i; } while (a[i] < pivot);
        do { --j; } while (a[j] > pivot);
        if (i >= j) return j;
        std::swap(a[i], a[j]);
    }
}

void quicksortHoare(std::vector<int>& a, int lo, int hi) {
    if (lo < hi) {
        int p = hoarePartition(a, lo, hi);
        quicksortHoare(a, lo, p);
        quicksortHoare(a, p + 1, hi);
    }
}

int main() {
    std::vector<int> data{29, 10, 14, 37, 13, 5, 41, 22};
    auto a = data, b = data, c = data;

    quicksortLomuto(a, 0, static_cast<int>(a.size()) - 1);
    quicksortHoare(b, 0, static_cast<int>(b.size()) - 1);
    std::sort(c.begin(), c.end());          // what production code should use

    for (int v : a) std::cout << v << ' ';
    std::cout << '\n';
}

Java

// Quicksort in Java 17
// Compile: javac Quicksort.java   Run: java Quicksort
import java.util.Arrays;

public class Quicksort {

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    private static int lomutoPartition(int[] a, int lo, int hi) {
        int pivot = a[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; j++)
            if (a[j] < pivot)
                swap(a, ++i, j);
        swap(a, i + 1, hi);
        return i + 1;
    }

    public static void quicksortLomuto(int[] a, int lo, int hi) {
        if (lo < hi) {
            int p = lomutoPartition(a, lo, hi);
            quicksortLomuto(a, lo, p - 1);
            quicksortLomuto(a, p + 1, hi);
        }
    }

    private static int hoarePartition(int[] a, int lo, int hi) {
        int pivot = a[lo + (hi - lo) / 2];
        int i = lo - 1, j = hi + 1;
        while (true) {
            do { i++; } while (a[i] < pivot);
            do { j--; } while (a[j] > pivot);
            if (i >= j) return j;
            swap(a, i, j);
        }
    }

    public static void quicksortHoare(int[] a, int lo, int hi) {
        if (lo < hi) {
            int p = hoarePartition(a, lo, hi);
            quicksortHoare(a, lo, p);
            quicksortHoare(a, p + 1, hi);
        }
    }

    public static void main(String[] args) {
        int[] data = {29, 10, 14, 37, 13, 5, 41, 22};
        int[] a = data.clone(), b = data.clone();

        quicksortLomuto(a, 0, a.length - 1);
        quicksortHoare(b, 0, b.length - 1);

        System.out.println("Lomuto: " + Arrays.toString(a));
        System.out.println("Hoare:  " + Arrays.toString(b));
    }
}

Lomuto: [5, 10, 13, 14, 22, 29, 37, 41]
Hoare:  [5, 10, 13, 14, 22, 29, 37, 41]

Python

"""Quicksort in Python 3 - Lomuto and Hoare partition schemes."""


def lomuto_partition(a, lo, hi):
    """Pivot is the last element. Returns the pivot's final index."""
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1


def quicksort_lomuto(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = lomuto_partition(a, lo, hi)
        quicksort_lomuto(a, lo, p - 1)
        quicksort_lomuto(a, p + 1, hi)
    return a


def hoare_partition(a, lo, hi):
    """Two pointers moving inward. Returns a split point, not a pivot index."""
    pivot = a[lo + (hi - lo) // 2]
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot:
            i += 1
        j -= 1
        while a[j] > pivot:
            j -= 1
        if i >= j:
            return j
        a[i], a[j] = a[j], a[i]


def quicksort_hoare(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = hoare_partition(a, lo, hi)
        quicksort_hoare(a, lo, p)
        quicksort_hoare(a, p + 1, hi)
    return a


if __name__ == "__main__":
    data = [29, 10, 14, 37, 13, 5, 41, 22]
    print("Lomuto:  ", quicksort_lomuto(data.copy()))
    print("Hoare:   ", quicksort_hoare(data.copy()))
    print("sorted():", sorted(data))   # Timsort - what you should actually use

A Python caveat: the default recursion limit is 1,000 frames. Sorted input large enough to hit the degenerate case will raise RecursionError well before it would segfault in C. Use the smaller-side technique, raise the limit deliberately, or just use sorted().

C#

// Quicksort in C# - Lomuto and Hoare partition schemes.
using System;

class Quicksort
{
    static void Swap(int[] a, int i, int j)
    {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    static int LomutoPartition(int[] a, int lo, int hi)
    {
        int pivot = a[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; j++)
            if (a[j] < pivot)
                Swap(a, ++i, j);
        Swap(a, i + 1, hi);
        return i + 1;
    }

    public static void SortLomuto(int[] a, int lo, int hi)
    {
        if (lo < hi)
        {
            int p = LomutoPartition(a, lo, hi);
            SortLomuto(a, lo, p - 1);
            SortLomuto(a, p + 1, hi);
        }
    }

    static int HoarePartition(int[] a, int lo, int hi)
    {
        int pivot = a[lo + (hi - lo) / 2];
        int i = lo - 1, j = hi + 1;
        while (true)
        {
            do { i++; } while (a[i] < pivot);
            do { j--; } while (a[j] > pivot);
            if (i >= j) return j;
            Swap(a, i, j);
        }
    }

    public static void SortHoare(int[] a, int lo, int hi)
    {
        if (lo < hi)
        {
            int p = HoarePartition(a, lo, hi);
            SortHoare(a, lo, p);
            SortHoare(a, p + 1, hi);
        }
    }

    static void Main()
    {
        int[] data = { 29, 10, 14, 37, 13, 5, 41, 22 };
        int[] a = (int[])data.Clone(), b = (int[])data.Clone();

        SortLomuto(a, 0, a.Length - 1);
        SortHoare(b, 0, b.Length - 1);

        Console.WriteLine("Lomuto: " + string.Join(", ", a));
        Console.WriteLine("Hoare:  " + string.Join(", ", b));
    }
}

Use the Library Sort in Production

Every implementation above is for understanding the algorithm. Shipping code should call the standard library, which has spent decades absorbing edge cases you will not think of:

std::sort and Array.Sort use introsort, which begins as quicksort and switches to heapsort once recursion runs too deep — guaranteeing O(n log n) worst case while keeping quicksort’s speed on typical input. That is the engineering answer to everything described above, and it is why hand-rolled quicksort in production is almost always the wrong call.

Key Takeaways

• Hoare’s partition does 2.9× fewer swaps than Lomuto’s on random data (14,238 vs 40,743 on 5,000 elements) — which is why production sorts descend from it.
• They return different things. Lomuto returns the pivot’s final index; Hoare returns a split point. Mixing one scheme’s partition with the other’s recursive calls is the most common quicksort bug.
• The worst case is real. Last-element pivot on 5,000 sorted values: 12,497,500 comparisons — exactly n(n−1)/2 — against 66,807 for a middle pivot. A 187× difference from pivot choice alone.
• Naive recursion segfaults. 200,000 sorted elements crashed the stack; recursing into the smaller side survived.
• Median-of-three fails silently if you misplace the median — 2.3× more comparisons, with correct output hiding the bug.
• Quicksort is not stable, and in production you should call std::sort, Arrays.sort or sorted() rather than writing your own.

Frequently Asked Questions

Conclusion

The gap between quicksort-the-idea and quicksort-that-works is wider than most tutorials admit. The idea is four lines of pseudocode. The working version needs a pivot strategy that survives sorted input, the right pairing of partition scheme and recursive calls, and a recursion pattern that will not exhaust the stack — and the failure mode for two of those three is not a crash but a silent slowdown you would never notice in a unit test.

That is also why it repays study. Quicksort is the clearest case in introductory computer science where the asymptotic analysis, the implementation detail and the real measured runtime all interact — and where getting one of them wrong costs you a factor of 187 while still printing the right answer. Once it makes sense, the same partitioning idea turns up again in quickselect, in three-way partitioning for duplicate-heavy data, and in the introsort hybrid your standard library is already using. The algorithms section covers the neighbouring territory.