Quick Sort Algorithm Partition Pivot: Tutorial, Examples, FAQs & Interview Tips

What is Quick Sort?

Quick Sort is a divide-and-conquer sorting algorithm. It chooses a pivot, rearranges the array so that smaller elements go to one side and larger elements go to the other side, and then recursively sorts the two parts.

Quick Sort is one of the most important sorting algorithms because it is usually very fast in practice, has low overhead, and works in-place for arrays.

Core Idea

Quick Sort follows these steps:

Choose a pivot element.
Partition the array around the pivot.
Recursively sort the left part.
Recursively sort the right part.

After partitioning, the pivot reaches a position where all smaller elements are on one side and all larger elements are on the other side. That pivot does not need to be moved again.

Why Quick Sort Is Fast in Practice

Quick Sort is often faster than other O(n log n) algorithms in real systems because:

it has excellent cache locality,
it works in-place with low extra memory,
its inner loops are simple and efficient.

Even though Merge Sort and Heap Sort also achieve O(n log n), Quick Sort is often preferred for arrays when average-case speed matters most.

Time and Space Complexity

Case	Time	Recursion Stack	Stable?
Best	O(n log n)	O(log n)	No
Average	O(n log n)	O(log n)	No
Worst	O(n^2)	O(n)	No

The worst case happens when partitions are extremely unbalanced, such as sizes 0 and n - 1 repeatedly. This can happen with poor pivot choice, for example always choosing the last element in an already sorted array.

Why the Average Case Is O(n log n)

If the pivot usually splits the array into reasonably balanced parts, then each level of recursion processes a total of n elements, and there are about log n levels. That gives the average running time O(n log n).

Quick Sort performs badly only when the partitions become too unbalanced again and again.

Partitioning

Partitioning is the heart of Quick Sort. It rearranges the subarray so that:

elements smaller than the pivot go to the left,
elements larger than the pivot go to the right.

Different partition schemes do this in slightly different ways. The two most common are Lomuto partition and Hoare partition.

Quick Sort - Lomuto and Randomized Partition

import java.util.Arrays;

public class QuickSort {

    // Lomuto partition: pivot is the last element.
    static int partitionLomuto(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partitionLomuto(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // Hoare partition: fewer swaps in many cases.
    static int partitionHoare(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low - 1;
        int j = high + 1;

        while (true) {
            do { i++; } while (arr[i] < pivot);
            do { j--; } while (arr[j] > pivot);

            if (i >= j) return j;

            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("Before: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("After:  " + Arrays.toString(arr));
    }
}

import java.util.Arrays;
import java.util.Random;

public class RandomizedQuickSort {

    static Random rand = new Random();

    static int randomPartition(int[] arr, int low, int high) {
        int randomIndex = low + rand.nextInt(high - low + 1);

        int temp = arr[randomIndex];
        arr[randomIndex] = arr[high];
        arr[high] = temp;

        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = randomPartition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 8, 10, 1, 2, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

Lomuto vs Hoare Partition

Feature	Lomuto	Hoare
Pivot position	Usually last element	Often first element
Implementation	Simpler to understand	Slightly trickier
Swaps	Often more swaps	Often fewer swaps
Returned index	Final pivot position	Boundary index, not always pivot position
Usefulness	Great for teaching	Often more efficient in practice

Step-by-Step Example

Consider [10, 7, 8, 9, 1, 5] with pivot 5 using Lomuto partition.

Start with i = low - 1.
Scan the array from left to right.
When an element is less than or equal to the pivot, increase i and swap.
After scanning, place the pivot after the last smaller element.

One pass gives:

Initial array: [10, 7, 8, 9, 1, 5]
Only 1 is less than or equal to 5, so it moves left.
After final pivot swap: [1, 5, 8, 9, 10, 7]
Pivot 5 is now in its correct final position.

Now Quick Sort recursively sorts [1] and [8, 9, 10, 7].

Pivot Selection Strategies

Strategy	Pivot Choice	Worst Case Risk	Notes
First element	`arr[low]`	High on sorted input	Very simple
Last element	`arr[high]`	High on sorted input	Common in textbooks
Middle element	Middle index	Better than extremes in many cases	Simple heuristic
Median of three	Median of first, middle, last	Lower in practice	Common optimization
Random pivot	Random index	Very unlikely repeatedly	Gives expected O(n log n)

Randomized Quick Sort

Randomized Quick Sort picks the pivot randomly instead of using a fixed rule like first or last element. This helps avoid consistently bad partitions on already sorted or specially arranged input.

It does not remove the theoretical worst case, but it makes that worst case extremely unlikely for practical use.

Quick Sort and Duplicate Elements

Quick Sort can perform poorly when many elements are equal, especially with simple partition schemes. In such cases, a 3-way partition can help by dividing elements into:

less than pivot,
equal to pivot,
greater than pivot.

This reduces unnecessary recursive work on equal elements and improves performance for inputs with many duplicates.

Why Quick Sort Is Not Stable

A sorting algorithm is stable if equal elements remain in the same relative order after sorting. Quick Sort is generally not stable because partitioning may swap equal elements across the array.

Tail Recursion and Space Optimization

The recursion stack of Quick Sort is O(log n) on average but can become O(n) in the worst case. One common optimization is to recursively sort the smaller partition first and handle the larger one iteratively or through tail recursion. This helps reduce stack depth.

Quick Sort vs Merge Sort vs Heap Sort

Feature	Quick Sort	Merge Sort	Heap Sort
Best / Average	O(n log n)	O(n log n)	O(n log n)
Worst case	O(n^2)	O(n log n)	O(n log n)
Extra space	O(log n)	O(n)	O(1)
Stable	No	Yes	No
Practical performance	Usually fastest for arrays	Very reliable, good for linked lists and stable sorting	Predictable but often slower in practice

When to Use Quick Sort

Quick Sort is a good choice when:

you need fast average-case array sorting,
low extra memory usage matters,
stability is not required.

It is less suitable when guaranteed worst-case performance is required or when stable sorting is necessary.

Advantages of Quick Sort

Very fast on average.
Works in-place for arrays.
Excellent cache performance.
Widely used and heavily optimized in practice.

Limitations of Quick Sort

Worst-case time is O(n^2).
Not stable.
Performance depends heavily on pivot selection.
Simple versions can behave poorly on many duplicate keys.

Common Mistakes

Confusing partitioning with full sorting.
Choosing a bad fixed pivot and forgetting worst-case input.
Using Hoare partition but recursing with Lomuto-style indices.
Ignoring duplicate-heavy input cases.
Assuming Quick Sort is stable.

Key Takeaways

Quick Sort is a divide-and-conquer sorting algorithm based on partitioning around a pivot.
Its average time is O(n log n), but the worst case is O(n^2).
Good pivot selection is critical for performance.
Randomized and median-based pivot strategies reduce the risk of bad partitions.
Quick Sort is usually one of the fastest practical array-sorting algorithms.

Previous Next