Quick Sort in Java
Problem
Quick sort picks a pivot value, rearranges the array so smaller values sit before the pivot and larger ones after it, and then sorts those two sides the same way.
Given an array of integers, sort it in ascending order using quick sort.
Java Program
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {24, 9, 31, 5, 18, 2, 27};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
static void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
int p = partition(arr, low, high);
quickSort(arr, low, p - 1); // everything smaller than the pivot
quickSort(arr, p + 1, high); // everything larger than the pivot
}
// Lomuto partition: the last element is the pivot
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int boundary = low; // next slot for a value smaller than the pivot
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
swap(arr, boundary, j);
boundary++;
}
}
swap(arr, boundary, high); // drop the pivot right after the smaller values
return boundary;
}
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}Output
Core Logic
One partition step puts the pivot exactly where it belongs in the final sorted array, so the problem shrinks to sorting the two sides around it.
- 1
partitiontakes the last element,arr[high], as the pivot. - 2
boundarymarks where the next value smaller than the pivot should go; each such value found by the scan is swapped there. - 3After the scan, the pivot is swapped into
arr[boundary]— everything to its left is smaller, everything to its right is not. - 4
quickSortthen recurses onlow..p-1andp+1..high, stopping when a range has fewer than two elements.
27; the scan moves 24, 9, 5, 18 and 2 to the front, and 27 lands at index 5, its final sorted position.Key Point: With the last element as pivot, an already-sorted array produces the worst case: every partition peels off just one element, and the time degrades to O(n²) — choosing a middle or random pivot avoids this.
Why: Balanced partitions halve the range about log n times with O(n) work per level; the recursion stack is the only extra memory, and it grows to n levels in the worst case.
Key Concepts
Approach 2: Hoare Partition (Middle Pivot)
import java.util.Arrays;
public class QuickSortHoare {
public static void main(String[] args) {
int[] arr = {24, 9, 31, 5, 18, 2, 27};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
static void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
int split = partition(arr, low, high);
quickSort(arr, low, split); // split stays in the left half with Hoare's scheme
quickSort(arr, split + 1, high);
}
// Hoare partition with the middle element as pivot
static int partition(int[] arr, int low, int high) {
int pivot = arr[low + (high - low) / 2];
int i = low - 1, j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot); // find a value that belongs on the right
do { j--; } while (arr[j] > pivot); // find a value that belongs on the left
if (i >= j) return j; // the scans crossed, so the split point is j
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
Output
Core Logic
Hoare's original scheme scans inward from both ends at once and swaps pairs that are on the wrong side, which usually performs fewer swaps than the Lomuto scheme.
- 1The pivot is the middle element,
arr[low + (high - low) / 2], which handles sorted input well. - 2
imoves right past values smaller than the pivot;jmoves left past values larger than it. - 3When both stop,
arr[i]andarr[j]are on the wrong sides, so they are swapped. - 4Once the pointers cross,
jis the split point, and the recursion sortslow..jandj+1..high.
[24, 9, 31, 5, 18, 2, 27] the pivot is 5; i stops at 24 and j stops at 2, so they swap, and the scans continue until they cross.Key Point: Unlike Lomuto, Hoare's partition does not leave the pivot at its final index, so the left recursive call must include j itself — using j - 1 there would skip elements and leave the array unsorted.
Why: The partitioning work per level is still O(n), and the middle pivot makes the O(n²) case much less likely on sorted or reverse-sorted input.
Key Concepts
Interview Questions
What is the worst case for quick sort?
When every pivot splits the array very unevenly, such as picking the last element of an already sorted array. The time then becomes O(n²).
Is quick sort stable?
No. Partitioning swaps elements across long distances, so equal values can change order.