Quick Sort in Java

A PT teacher wants a line of students sorted by height. She picks one student, say Advitha, and says: "Everyone shorter than Advitha, stand on her left. Everyone taller, on her right." Advitha is now exactly where she belongs in the final line, even though neither side is sorted yet. The teacher then repeats the same trick on the left group and on the right group. That is quick sort: pick a pivot, partition everything around it, and repeat on each side. It is one of the fastest sorting algorithms in practice. In this lesson, you will learn how partitioning works, write quick sort in Java with a trace, and see its best and worst cases.

What Is Quick Sort?

Quick sort in Java is a divide and conquer sorting algorithm that is used to sort an array by choosing a pivot element, partitioning the array so that smaller elements come before the pivot and larger ones after it, and then recursively sorting the two parts.

• It sorts in place, needing only O(log n) stack space on average.
• It is O(n log n) on average and very fast in practice.
• It is O(n²) in the worst case, when the pivot is always the smallest or largest element.
• It is not stable.
• Java's Arrays.sort for primitive arrays uses a dual-pivot quick sort.

How It Works

1. Choose a pivot. This lesson uses the last element (the Lomuto scheme).
2. Partition: walk through the range, and move every element less than or equal to the pivot to the front part. Then swap the pivot right after that front part. The pivot is now in its final position.
3. Recurse on the part left of the pivot and the part right of it.
4. A part with 0 or 1 elements is already sorted.

Quick Sort in Java

Let's see an example that sorts the array from the picture and prints every partition.

import java.util.Arrays;
 
public class QuickSort {
    static void quickSort(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int p = partition(a, low, high);
        System.out.println("pivot " + a[p] + " placed at " + p + ": "
                + Arrays.toString(a));
        quickSort(a, low, p - 1);
        quickSort(a, p + 1, high);
    }
 
    static int partition(int[] a, int low, int high) {
        int pivot = a[high];
        int i = low - 1;                   // end of the "small" part
        for (int j = low; j < high; j++) {
            if (a[j] <= pivot) {
                i++;
                swap(a, i, j);
            }
        }
        swap(a, i + 1, high);              // pivot goes right after it
        return i + 1;
    }
 
    static void swap(int[] a, int x, int y) {
        int t = a[x];
        a[x] = a[y];
        a[y] = t;
    }
 
    public static void main(String[] args) {
        int[] heights = {29, 10, 14, 37, 13, 25};
        quickSort(heights, 0, heights.length - 1);
        System.out.println("sorted: " + Arrays.toString(heights));
    }
}

pivot 25 placed at 3: [10, 14, 13, 25, 29, 37]
pivot 13 placed at 1: [10, 13, 14, 25, 29, 37]
pivot 37 placed at 5: [10, 13, 14, 25, 29, 37]
sorted: [10, 13, 14, 25, 29, 37]

Explanation:

1. The first partition uses 25 as the pivot and gives [10, 14, 13, 25, 29, 37], exactly as in the picture. 25 is at index 3 and will never move again.
2. Quick sort then works on the left part [10, 14, 13] with pivot 13, and on the right part [29, 37] with pivot 37.
3. In partition, i marks the end of the "less than or equal" part. Every time a[j] belongs there, i grows and a[j] is swapped in.
4. Unlike merge sort, the work happens before the recursive calls, and no extra array is needed.

Best, Average and Worst Case

The speed depends on how evenly the pivot splits the array.

Let's see the worst case happen: on sorted input, the last element is always the largest, so each partition peels off only one element.

public class WorstCase {
    static long comparisons = 0;
 
    static void quickSort(int[] a, int low, int high) {
        if (low >= high) return;
        int pivot = a[high], i = low - 1;
        for (int j = low; j < high; j++) {
            comparisons++;
            if (a[j] <= pivot) {
                i++;
                int t = a[i]; a[i] = a[j]; a[j] = t;
            }
        }
        int t = a[i + 1]; a[i + 1] = a[high]; a[high] = t;
        quickSort(a, low, i);
        quickSort(a, i + 2, high);
    }
 
    static long run(int[] a) {
        comparisons = 0;
        quickSort(a, 0, a.length - 1);
        return comparisons;
    }
 
    public static void main(String[] args) {
        int n = 1000;
        int[] sorted = new int[n];
        int[] mixed = new int[n];
        for (int k = 0; k < n; k++) {
            sorted[k] = k;
            mixed[k] = (k * 7919) % n;    // a scrambled order
        }
        System.out.println("sorted input: " + run(sorted));
        System.out.println("mixed input:  " + run(mixed));
    }
}

sorted input: 499500
mixed input:  11414

Explanation: on sorted input, quick sort makes about n² / 2 comparisons, almost 500,000 for 1,000 elements. On scrambled input, it makes about 11,400, more than 40 times fewer. Real implementations avoid the worst case by choosing the pivot more carefully: a random element, or the median of three (first, middle and last).

Quick Sort vs Merge Sort

Interview Corner

Practice

1. Easy: Change partition to sort in descending order by changing one comparison. Test it on {29, 10, 14, 37, 13, 25}.
2. Harder: Before partitioning, swap a random element between low and high into position high (use java.util.concurrent.ThreadLocalRandom). Run WorstCase again and compare the comparison count on sorted input.

Key Takeaways