Quick Sort O(n²) — Sorted Input Breaks Last-Element Pivot

Every time you search for a product on Amazon, sort a playlist by play count, or watch a leaderboard update in real time, a sorting algorithm is doing invisible heavy lifting. Quick Sort is one of the most widely deployed sorting algorithms in the world — it powers the default sort in many standard libraries (including older versions of Java's Arrays.sort for primitives) and consistently outperforms its rivals on real hardware. Understanding it isn't just academic; it directly shapes how you write high-performance code.

The problem Quick Sort solves is deceptively simple: given an unordered collection, arrange its elements in order as fast as possible. What makes sorting hard isn't the goal — it's the cost. Naive approaches like Bubble Sort touch every pair of elements, which becomes catastrophically slow as data grows. Quick Sort instead uses a divide-and-conquer strategy: it shrinks the problem recursively so that each step does just enough work to guarantee permanent progress, achieving an average-case time complexity of O(n log n).

By the end of this article you'll understand exactly how Quick Sort's partitioning step works (not just what it does), why pivot choice is the difference between blazing speed and worst-case disaster, how to implement it cleanly in Java with a Lomuto partition scheme, and — critically — when you should reach for it versus Merge Sort or Tim Sort in production code.

Quick Sort's Dirty Secret: Sorted Input Kills Performance

Quick sort is a divide-and-conquer sorting algorithm that picks a pivot element, partitions the array so that elements smaller than the pivot go left and larger go right, then recursively sorts the two partitions. Its average-case time complexity is O(n log n), but with a naive last-element pivot on an already sorted array, it degrades to O(n²) — the same as bubble sort.

The algorithm's performance hinges entirely on pivot selection. When the pivot is always the smallest or largest element, each partition splits off only one element, producing n recursive calls and n comparisons per call. This turns a fast O(n log n) sort into a quadratic disaster. In practice, this means quick sort is only as good as its pivot strategy — random or median-of-three pivots are essential for consistent performance.

Use quick sort when you need an in-place sort with good average-case speed and can tolerate O(n²) worst-case. It's the default in many standard libraries (e.g., Java's Arrays.sort for primitives) because its constant factors are low and it uses minimal extra memory. But never assume it's safe on all inputs — always verify your pivot choice against your data's distribution.

The Partition Step: The One Idea That Makes Everything Click

Quick Sort has one core insight: if you can place a single element — the pivot — into its exact final sorted position in one pass, you've permanently reduced your problem. Everything to the left of the pivot is smaller; everything to the right is larger. Neither side needs to know about the other. That's the partition step, and it's the whole algorithm.

The Lomuto partition scheme (the cleanest version for learning) walks a pointer storeIndex through the array. Whenever it finds an element smaller than or equal to the pivot, it swaps that element forward past the boundary. At the end, the pivot swaps into storeIndex. The pivot is now home — forever.

Why does this work so well? Because it's in-place. No extra array needed. Every swap is local. Modern CPUs love this because the data stays in cache. Merge Sort is theoretically equivalent at O(n log n), but it needs O(n) extra memory and its cache access pattern is less friendly. Quick Sort wins in practice because the hardware rewards it.

The recursive calls on the left and right sub-arrays are then completely independent. They don't share state. That independence is also why Quick Sort parallelises beautifully — each partition can run on a separate thread.

public class QuickSortLomuto {

    /**
     * Entry point — sorts the array in-place between indices 'low' and 'high'.
     * We pass indices rather than creating sub-arrays, so no extra memory is needed.
     */
    public static void quickSort(int[] numbers, int low, int high) {
        // Base case: a sub-array of 0 or 1 elements is already sorted — nothing to do.
        if (low >= high) return;

        // Partition the array and get back the pivot's final resting index.
        int pivotFinalIndex = partition(numbers, low, high);

        // Recursively sort everything to the LEFT of the pivot (pivot itself is already placed).
        quickSort(numbers, low, pivotFinalIndex - 1);

        // Recursively sort everything to the RIGHT of the pivot.
        quickSort(numbers, pivotFinalIndex + 1, high);
    }

    /**
     * Lomuto Partition Scheme.
     * Chooses the LAST element as the pivot, then rearranges the sub-array so that:
     *   - All elements <= pivot are to the left of storeIndex
     *   - All elements >  pivot are to the right of storeIndex
     * Returns storeIndex — the pivot's correct final position.
     */
    private static int partition(int[] numbers, int low, int high) {
        int pivot = numbers[high]; // We always pick the last element as pivot (simple but has pitfalls — see Gotchas)
        int storeIndex = low - 1; // storeIndex tracks the boundary between "small" and "large" elements

        for (int scanner = low; scanner < high; scanner++) {
            if (numbers[scanner] <= pivot) {
                storeIndex++;  // Expand the "small" region by one slot
                swap(numbers, storeIndex, scanner); // Pull this small element into the small region
            }
        }

        // Place the pivot right after all the small elements — this is its final position.
        swap(numbers, storeIndex + 1, high);

        return storeIndex + 1; // Return the pivot's final index so quickSort knows where to split
    }

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

    public static void main(String[] args) {
        int[] scores = {42, 17, 93, 5, 61, 38, 72, 29};

        System.out.println("Before sorting:");
        printArray(scores);

        quickSort(scores, 0, scores.length - 1);

        System.out.println("After sorting:");
        printArray(scores);
    }

    private static void printArray(int[] numbers) {
        System.out.print("[ ");
        for (int number : numbers) System.out.print(number + " ");
        System.out.println("]");
    }
}

Visual Partition Diagram — Pivot Placement and Element Movement

To truly internalise how Lomuto partition works, trace it visually. Consider the array [8, 3, 1, 5, 2] with pivot = 2 (last element). The partition step moves all elements ≤ pivot to the left, then inserts the pivot into its final position.

Step-by-step visual:

Initial: [8, 3, 1, 5, 2] pivot=2, storeIndex=-1

Scan j=0 (value 8 > 2): no swap. Index: [8, 3, 1, 5, 2] storeIndex=-1

j=1 (value 3 > 2): no swap. [8, 3, 1, 5, 2] storeIndex=-1

j=2 (value 1 ≤ 2): storeIndex→0, swap arr[0] and arr[2]. [1, 3, 8, 5, 2] storeIndex=0

j=3 (value 5 > 2): no swap. [1, 3, 8, 5, 2] storeIndex=0

Final: swap pivot (arr[4]=2) with arr[storeIndex+1]=arr[1]=3. [1, 2, 8, 5, 3] pivot now at index 1 (final position).

What the diagram shows: The elements in the blue region (indices ≤ storeIndex) are all ≤ pivot. After placing the pivot, it acts as a barrier: left subarray [1] and right subarray [8,5,3] are independent and never cross again.

This visualisation is the secret to debugging Quick Sort: if the pivot doesn't end up exactly at the returned index, the partition logic is wrong.

   Before partition: [8, 3, 1, 5, 2]   pivot=2
   storeIndex = -1 (no small region yet)
   
   j=0: 8>2 → skip
   j=1: 3>2 → skip
   j=2: 1≤2 → storeIndex=0, swap(0,2) → [1, 3, 8, 5, 2]
   j=3: 5>2 → skip
   
   Place pivot: swap(arr[storeIndex+1], arr[high]) → swap(1,4) → [1, 2, 8, 5, 3]
   
   Final: pivot at index 1. Left=[1], Right=[8,5,3]

Pivot Choice: Why 'Last Element' Is a Trap on Sorted Data

The pivot choice is the single biggest lever you have over Quick Sort's performance. Pick well, and you split the array roughly in half every time — O(n log n). Pick badly, and every partition produces one empty side and one side with n-1 elements — that's O(n²), as slow as Bubble Sort.

The worst case for 'always pick last element' is a sorted or reverse-sorted array. Every partition selects the largest (or smallest) remaining element, the splits are maximally unbalanced, and you make n recursive calls instead of log n. This is a real production bug, not a theoretical one — pre-sorted input is extremely common in real data.

The fix used in production is the median-of-three strategy: look at the first, middle, and last elements of the sub-array, pick the median value as your pivot, and swap it to the last position before running Lomuto as normal. This dramatically reduces the probability of worst-case behaviour on sorted, reverse-sorted, or nearly-sorted data.

Java's Arrays.sort for primitive types uses a Dual-Pivot Quick Sort (introduced in Java 7), which picks two pivots and creates three partitions. It's even harder to degrade to O(n²) and squeezes better cache performance out of modern CPUs. The lesson: the partition scheme is just a starting point. Production implementations have 30+ years of refinement baked in.

public class QuickSortMedianOfThree {

    public static void quickSort(int[] numbers, int low, int high) {
        if (low >= high) return;

        // Choose a smarter pivot BEFORE partitioning
        choosePivotMedianOfThree(numbers, low, high);

        int pivotFinalIndex = partition(numbers, low, high);
        quickSort(numbers, low, pivotFinalIndex - 1);
        quickSort(numbers, pivotFinalIndex + 1, high);
    }

    /**
     * Median-of-Three Pivot Selection.
     * Looks at the first, middle, and last elements.
     * Rearranges so the median value ends up at numbers[high] — ready for Lomuto.
     * This prevents O(n²) behaviour on already-sorted input.
     */
    private static void choosePivotMedianOfThree(int[] numbers, int low, int high) {
        int mid = low + (high - low) / 2; // Avoids integer overflow (important for large arrays)

        // Sort just these three candidates so numbers[mid] holds the median
        if (numbers[low] > numbers[mid])  swap(numbers, low, mid);
        if (numbers[low] > numbers[high]) swap(numbers, low, high);
        if (numbers[mid] > numbers[high]) swap(numbers, mid, high);

        // Now numbers[high] is the median of the three — perfect Lomuto pivot
    }

    private static int partition(int[] numbers, int low, int high) {
        int pivot = numbers[high];
        int storeIndex = low - 1;

        for (int scanner = low; scanner < high; scanner++) {
            if (numbers[scanner] <= pivot) {
                storeIndex++;
                swap(numbers, storeIndex, scanner);
            }
        }

        swap(numbers, storeIndex + 1, high);
        return storeIndex + 1;
    }

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

    public static void main(String[] args) {
        // This input would cause O(n²) with naive last-element pivot — median-of-three handles it fine
        int[] alreadySorted = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

        System.out.println("Sorting already-sorted data (Quick Sort's classic nemesis):");
        System.out.print("Before: ");
        printArray(alreadySorted);

        quickSort(alreadySorted, 0, alreadySorted.length - 1);

        System.out.print("After:  ");
        printArray(alreadySorted);

        // Also demonstrate on random data
        int[] playerScores = {88, 34, 67, 12, 99, 45, 23, 78, 56, 11};
        System.out.println("\nSorting game leaderboard scores:");
        System.out.print("Before: ");
        printArray(playerScores);

        quickSort(playerScores, 0, playerScores.length - 1);

        System.out.print("After:  ");
        printArray(playerScores);
    }

    private static void printArray(int[] numbers) {
        System.out.print("[ ");
        for (int n : numbers) System.out.print(n + " ");
        System.out.println("]");
    }
}

Implementations in Python and C++

Quick Sort is language-agnostic, but idioms differ. Here are clean implementations in Python and C++ using Lomuto partition with last-element pivot for clarity. In production, always pair these with median-of-three or random pivot selection.

Python (idiomatic, no explicit recursion limit needed for small arrays):

```python def quicksort(arr, low, high): if low >= high: return pivot_index = partition(arr, low, high) quicksort(arr, low, pivot_index - 1) quicksort(arr, pivot_index + 1, high)

def partition(arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 ```

C++ (template for generic types, in-place):

```cpp template<typename T> void quickSort(T arr[], int low, int high) { if (low >= high) return; int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); }

template<typename T> int partition(T arr[], int low, int high) { T pivot = arr[high]; int i = low - 1; for (int j = low; j < high; ++j) { if (arr[j] <= pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } ```

Both implementations follow the same Lomuto logic: scan with i tracking the small region, swap when arr[j] <= pivot, and finally place the pivot. The C++ template works for any type with operator<= — often paired with std::sort (Introsort) in real code.

Quick Sort vs Merge Sort: Choosing the Right Tool for the Job

Quick Sort and Merge Sort both hit O(n log n) average case, so why does it matter which you pick? Because 'average case' hides a lot of nuance that matters enormously in production.

Quick Sort is faster in practice for most general-purpose in-memory sorting because its inner loop does very little work per comparison, it accesses memory sequentially (cache-friendly), and it needs no extra allocation. Its weak spot is its worst case: a bad pivot strategy on degenerate input can hit O(n²) — and unlike Merge Sort's worst case, this can actually happen with real data.

Merge Sort is the right choice when stability matters. A stable sort preserves the original relative order of equal elements. This is crucial when you're sorting objects by one field and the objects already have a meaningful order by another field — like sorting employees by department when they're already ordered by hire date. Merge Sort is always O(n log n), no exceptions.

Java's Collections.sort (and Arrays.sort for objects) uses Tim Sort — a hybrid of Merge Sort and Insertion Sort that is stable, adaptive to partially-sorted data, and O(n log n) worst case. Use it by default. Only reach for a custom Quick Sort when you're sorting primitives, profiling shows a bottleneck, and you understand your data's distribution.

import java.util.Arrays;
import java.util.Comparator;

public class SortingComparison {

    // A real-world object: an employee with two sortable fields
    static class Employee {
        String name;
        String department;
        int hireOrder; // Lower = hired earlier (already sorted by this field)

        Employee(String name, String department, int hireOrder) {
            this.name = name;
            this.department = department;
            this.hireOrder = hireOrder;
        }

        @Override
        public String toString() {
            return name + "(" + department + ", hire#" + hireOrder + ")";
        }
    }

    public static void main(String[] args) {
        // Employees are already ordered by hireOrder (1 through 6)
        Employee[] employees = {
            new Employee("Alice",   "Engineering", 1),
            new Employee("Bob",     "Marketing",   2),
            new Employee("Carol",   "Engineering", 3),
            new Employee("David",   "Marketing",   4),
            new Employee("Eve",     "Engineering", 5),
            new Employee("Frank",   "Marketing",   6)
        };

        System.out.println("Original order (sorted by hire date):");
        printEmployees(employees);

        // Sort by department using Arrays.sort — which uses TimSort (STABLE) for objects
        Arrays.sort(employees, Comparator.comparing(e -> e.department));

        System.out.println("\nAfter sorting by department (TimSort — STABLE):");
        printEmployees(employees);
        // Notice: within Engineering, Alice(1) still comes before Carol(3) before Eve(5)
        // Their hire order is PRESERVED. This is what stable sort guarantees.

        System.out.println("\nWithin each department, hire order is preserved — that's stability in action.");

        // For primitives, Arrays.sort uses Dual-Pivot QuickSort (NOT stable, but very fast)
        int[] responseTimes = {120, 45, 300, 89, 12, 456, 67, 23};
        System.out.println("\nAPI response times (ms) before sort: " + Arrays.toString(responseTimes));
        Arrays.sort(responseTimes); // Dual-Pivot QuickSort under the hood
        System.out.println("API response times (ms) after sort:  " + Arrays.toString(responseTimes));
    }

    private static void printEmployees(Employee[] employees) {
        for (Employee e : employees) System.out.print(e + "  ");
        System.out.println();
    }
}

Advantages and Disadvantages of Quick Sort

Quick Sort is not a silver bullet. Here's a balanced look at its strengths and weaknesses for production decision-making.

Use Quick Sort when: sorting primitives, memory is constrained, data is random, and stability is irrelevant. Avoid it when: worst-case guarantee is required, stability matters, or the input is large and linked-list-based.

Worked Example — Tracing Quick Sort on [8, 3, 1, 5, 2]

Input: [8, 3, 1, 5, 2]. Pivot = last element = 2.

Partition step (pivot=2): i starts at -1 (left boundary of 'less than pivot' region). j=0: arr[0]=8 > 2. No swap. i stays at -1. j=1: arr[1]=3 > 2. No swap. i stays at -1. j=2: arr[2]=1 <= 2. i=0. Swap arr[0] and arr[2]. Array: [1, 3, 8, 5, 2]. j=3: arr[3]=5 > 2. No swap. Final: swap pivot (arr[4]=2) with arr[i+1]=arr[1]=3. Array: [1, 2, 8, 5, 3]. Pivot 2 is now at index 1. Everything left of index 1 is <= 2. Everything right is > 2.

Recurse left: sort [1] — single element, already sorted. Recurse right: sort [8, 5, 3]. Pivot = 3. j=0: 8>3. No swap. j=1: 5>3. No swap. Swap pivot arr[2]=3 with arr[0+1-1+1]=arr[0]... wait, i=-1, so swap arr[i+1]=arr[0]=8 with pivot arr[2]=3. Array: [3, 5, 8]. Pivot 3 at index 0. Recurse left: [] (empty). Recurse right: sort [5, 8]. Pivot=8. i=-1. j=0: 5<=8, swap arr[0] with arr[0], i=0. Place pivot: arr[1]=8 stays. [5,8].

Final array: [1, 2, 3, 5, 8]

Key observation: after each partition, the pivot is in its exact final sorted position. No element ever moves across a pivot after it is placed.

Library Sort Implementations: Dual‑Pivot QuickSort and Introsort

Production developers rarely write custom Quick Sort — they rely on battle-tested library functions that handle edge cases transparently.

Java's Arrays.sort() for primitives uses Dual‑Pivot QuickSort (since Java 7). It picks two pivots and partitions into three regions: elements < pivot1, between pivot1 and pivot2, and > pivot2. This reduces comparisons by ~20% and is extremely hard to push into O(n²). For object arrays, Arrays.sort() uses TimSort (stable merge‑sort hybrid).

C++'s std::sort() uses Introsort, which begins with Quick Sort but monitors recursion depth. If depth exceeds 2 * log2(n), it switches to Heap Sort for that partition — guaranteeing O(n log n) worst-case without the memory overhead of Merge Sort. This means std::sort is safe on sorted input, reversed data, and even randomly shuffled data.

// io.thecodeforge — dsa tutorial

int medianOfThree(int[] data, int left, int right) {
    int mid = left + (right - left) / 2;

    // Sort left, mid, right by value
    if (data[left] > data[mid]) swap(data, left, mid);
    if (data[left] > data[right]) swap(data, left, right);
    if (data[mid] > data[right]) swap(data, mid, right);

    // Median is now at mid — swap to right-1 for partitioning
    swap(data, mid, right - 1);
    return data[right - 1];
}

void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// io.thecodeforge — dsa tutorial

void tailRecursiveQuickSort(int[] data, int low, int high) {
    while (low < high) {
        int pivotIndex = partition(data, low, high);

        // Recurse on smaller half, iterate the larger one
        if (pivotIndex - low < high - pivotIndex) {
            tailRecursiveQuickSort(data, low, pivotIndex - 1);
            low = pivotIndex + 1;  // move to right half
        } else {
            tailRecursiveQuickSort(data, pivotIndex + 1, high);
            high = pivotIndex - 1; // move to left half
        }
    }
    // While loop replaces second recursive call
}

int partition(int[] arr, int l, int r) { /* Lomuto or Hoare */ return 0; }

// io.thecodeforge — dsa tutorial

import java.util.concurrent.*;

class ParallelQuickSort extends RecursiveAction {
    private static final int THRESHOLD = 5000;
    private final int[] data;
    private final int low, high;

    ParallelQuickSort(int[] data, int low, int high) {
        this.data = data;
        this.low = low;
        this.high = high;
    }

    @Override
    protected void compute() {
        if (high - low < THRESHOLD) {
            sequentialQuickSort(data, low, high);
            return;
        }
        int pivot = partition(data, low, high);
        invokeAll(
            new ParallelQuickSort(data, low, pivot - 1),
            new ParallelQuickSort(data, pivot + 1, high)
        );
    }
}

// io.thecodeforge — dsa tutorial

public class StackDepthWitness {
    static int depth = 0;
    static int maxDepth = 0;

    static void quickSort(int[] arr, int lo, int hi) {
        depth++;
        maxDepth = Math.max(maxDepth, depth);
        if (lo < hi) {
            int p = partition(arr, lo, hi);
            quickSort(arr, lo, p - 1);
            quickSort(arr, p + 1, hi);
        }
        depth--;
    }

    static int partition(int[] arr, int lo, int hi) {
        int pivot = arr[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; j++) {
            if (arr[j] <= pivot) {
                i++;
                int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            }
        }
        int tmp = arr[i + 1]; arr[i + 1] = arr[hi]; arr[hi] = tmp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Max depth on sorted input: " + maxDepth);
    }
}

// io.thecodeforge — dsa tutorial

public class CachePatternDemo {
    // Simulated in-place partition — sequential access wins
    static long partitionSequential(int[] arr, int n) {
        long sum = 0;
        for (int i = 0; i < n / 2; i++) {
            sum += arr[i];
            sum += arr[n - 1 - i];
        }
        return sum;
    }

    static long mergeRandomAccess(int[] arr, int[] aux, int n) {
        long sum = 0;
        for (int i = 0; i < n; i++) {
            // Merge sort auxiliary access pattern
            aux[i] = arr[i / 2] + arr[n - 1 - i / 2];
            sum += aux[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        int n = 1_000_000;
        int[] arr = new int[n];
        int[] aux = new int[n];
        long start = System.nanoTime();
        partitionSequential(arr, n);
        long t1 = System.nanoTime() - start;
        start = System.nanoTime();
        mergeRandomAccess(arr, aux, n);
        long t2 = System.nanoTime() - start;
        System.out.println("Sequential (quick): " + t1 / 1e6 + " ms");
        System.out.println("Random (merge):    " + t2 / 1e6 + " ms");
    }
}