Quicksort

›Short versionOpen if you only have a minute.

Pick a pivot, partition the range into smaller values and larger values, and sort the two sides by the same method.
The Lomuto partition below is unstable. A swap can move an equal key past another equal key.
The array is rearranged in the same storage. Extra memory is the recursion stack: logarithmic when splits stay balanced, linear when every pivot is extreme.
The worst case is quadratic. A sorted array with the last element as pivot shrinks the problem by only one each call. Balanced splits average n log n.
Arrays.sort on a primitive array is a JDK dual-pivot quicksort. Arrays.sort on objects is Timsort, which is stable and keeps a worst case of n log n.

Partition, then two smaller ranges

The code takes the last element of the range as the pivot. The index i marks the end of the region known to be smaller than the pivot. Each j that holds a smaller value is swapped into that region. When the scan finishes, the pivot swaps into the gap at i + 1. Everything to its left is smaller. Everything to its right is greater or equal. The two sides are sorted by recursion, and the pivot stays where the partition put it.

On [10, 7, 8, 9, 1, 5] the pivot is 5. Only 1 is smaller, so the partition ends as [1, 5, 8, 9, 10, 7]. The left side is a single element. The right side is sorted by the same steps.

Unstable, and the stack is the extra memory

This quicksort is . Stability is a property you need for records that compare equal and still have an identity. An int array hides the problem, because equal ints are the same value. The swaps are still there.

The values themselves stay inside the input array, so the sort is . Average time on random data is O(n log n). The worst case is O(n²), paired with that linear stack.

The input is already sorted, and the pivot is always the last element. How much smaller is the next recursive problem?

One element smaller. Every value is less than the pivot, so the partition plants the pivot at the end and leaves a subproblem of length n − 1. The depth is n, and the total work is quadratic. The same pattern appears on a reversed array with this pivot choice.

When the library sort takes over

For an int[], long[], or another primitive array, Arrays.sort is a . For objects, Arrays.sort and Collections.sort run . The method below is for seeing a partition. The library method is the one to call.

QuickSort.java

public class QuickSort {
    static void sort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivotIndex = partition(arr, low, high);
        sort(arr, low, pivotIndex - 1);
        sort(arr, pivotIndex + 1, high);
    }

    static int partition(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;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        sort(arr, 0, arr.length - 1);
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}