Java Program for Quick Sort with Example and Explanation

A Java program for quick sort uses a partition method to divide the array and recursively sorts subarrays; for example, quickSort(arr, 0, arr.length - 1) sorts the entire array in place.

Examples

Input[5, 3, 8, 4, 2]

Output[2, 3, 4, 5, 8]

Input[10, 7, 8, 9, 1, 5]

Output[1, 5, 7, 8, 9, 10]

Input[]

Output[]

How to Think About It

To sort an array using quick sort, pick a pivot element and rearrange the array so that elements less than the pivot come before it and elements greater come after. Then, apply the same process to the left and right parts recursively until the whole array is sorted.

Algorithm

1

Choose the last element as pivot.

2

Partition the array so elements less than pivot are left, greater are right.

3

Recursively apply quick sort to the left subarray.

4

Recursively apply quick sort to the right subarray.

5

Stop when subarray has one or no elements.

Code

java

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private 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};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Output

1 5 7 8 9 10 

Dry Run

Let's trace the array [10, 7, 8, 9, 1, 5] through the quick sort code.

1

Initial call

quickSort called with low=0, high=5, array=[10,7,8,9,1,5]

2

Partitioning

Pivot=5; rearranged array after partition: [1, 5, 8, 9, 10, 7]; pivot index=1

3

Left subarray sort

quickSort called with low=0, high=0 (single element), returns immediately

4

Right subarray sort

quickSort called with low=2, high=5, array=[8,9,10,7]

5

Partitioning right subarray

Pivot=7; rearranged array: [1,5,7,9,10,8]; pivot index=2

6

Sort left of pivot in right subarray

quickSort called with low=2, high=1 (empty), returns

7

Sort right of pivot in right subarray

quickSort called with low=3, high=5, array=[9,10,8]

8

Partitioning last subarray

Pivot=8; rearranged array: [1,5,7,8,10,9]; pivot index=3

9

Sort left and right of pivot

quickSort called with low=3, high=2 and low=4, high=5; left returns immediately; right sorts [10,9]

10

Final partition

Pivot=9; rearranged array: [1,5,7,8,9,10]; pivot index=4

11

Final recursive calls

quickSort called with low=4, high=3 and low=5, high=5; both return immediately

Step	Array State	Pivot	Pivot Index
1	[10,7,8,9,1,5]	5	1
2	[1,5,8,9,10,7]	7	2
3	[1,5,7,9,10,8]	8	3
4	[1,5,7,8,10,9]	9	4
5	[1,5,7,8,9,10]	-	-

Why This Works

Step 1: Choosing a pivot

The code picks the last element as the pivot to divide the array into smaller and larger parts.

Step 2: Partitioning the array

Elements smaller than the pivot are moved to the left, and larger ones to the right, placing the pivot in its correct sorted position.

Step 3: Recursive sorting

The quick sort function calls itself on the left and right parts around the pivot until the whole array is sorted.

Alternative Approaches

Randomized Quick Sort

java

import java.util.Random;
public class QuickSortRandom {
    private static final Random rand = new Random();
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = randomizedPartition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    private static int randomizedPartition(int[] arr, int low, int high) {
        int pivotIndex = low + rand.nextInt(high - low + 1);
        int temp = arr[pivotIndex];
        arr[pivotIndex] = arr[high];
        arr[high] = temp;
        return partition(arr, low, high);
    }
    private 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};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Random pivot reduces chance of worst-case performance but adds overhead.

Iterative Quick Sort

java

import java.util.Stack;
public class QuickSortIterative {
    public static void quickSort(int[] arr, int low, int high) {
        Stack<Integer> stack = new Stack<>();
        stack.push(low);
        stack.push(high);
        while (!stack.isEmpty()) {
            high = stack.pop();
            low = stack.pop();
            int pi = partition(arr, low, high);
            if (pi - 1 > low) {
                stack.push(low);
                stack.push(pi - 1);
            }
            if (pi + 1 < high) {
                stack.push(pi + 1);
                stack.push(high);
            }
        }
    }
    private 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};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Uses a stack to avoid recursion, useful when recursion depth is a concern.

Complexity: O(n log n) average, O(n^2) worst time, O(log n) average due to recursion stack space

Time Complexity

Quick sort divides the array and sorts subarrays recursively. On average, it takes O(n log n) because each partition splits the array roughly in half. Worst case is O(n^2) when pivot choices are poor.

Space Complexity

Quick sort sorts in place using the original array and uses O(log n) space for recursion stack in average cases.

Which Approach is Fastest?

Randomized quick sort reduces worst-case chances, iterative quick sort avoids recursion overhead, but classic recursive quick sort is simplest and efficient for most cases.

Approach	Time	Space	Best For
Classic Recursive Quick Sort	O(n log n) avg, O(n^2) worst	O(log n)	General use, simple code
Randomized Quick Sort	O(n log n) avg, better worst case	O(log n)	Avoid worst case on sorted inputs
Iterative Quick Sort	O(n log n) avg, O(n^2) worst	O(log n)	Avoid recursion stack overflow