Quick Sort

Medium20–25 min

Topics

SortingArrayDivide and ConquerRecursion

Companies

AmazonMicrosoftGoogleFlipkart

Given an array of integers, sort it in non-decreasing order using **Quick Sort** — pick a pivot, partition the array around it so every smaller value ends up on its left and every larger value on its right, then recursively sort each side. Unlike merge sort, quicksort does its work while partitioning rather than while merging, and it never needs to allocate a second array to combine results — everything happens in place. The catch is that its performance depends entirely on how well the chosen pivot splits the range each time, which is exactly what separates a naive implementation from a solid one.

Test Case 1:

Input:arr = [7, 2, 9, 4, 2, 8]

Output:[2, 2, 4, 7, 8, 9]

Explanation:A typical unsorted array with a repeated value.

Test Case 2:

Input:arr = []

Output:[]

Explanation:An empty array is already sorted.

Test Case 3:

Input:arr = [5]

Output:[5]

Explanation:A single element is already sorted.

Constraints

◆0 ≤ arr.length ≤ 200
◆-1000 ≤ arr[i] ≤ 1000
◆Sort in non-decreasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Last Element as Pivot

Good

Pick the last element of the current range as the pivot, then partition so everything ≤ pivot ends up to its left and everything greater ends up to its right — the pivot is now in its final sorted position. Recurse on both sides. This is the textbook Lomuto partition, and it's correct for any input — but always picking a fixed end as pivot means an already-sorted (or reverse-sorted) array makes every partition split off zero elements on one side, degrading to O(n²) with O(n) recursion depth on exactly the kind of input this shows up on most often.

TimeO(n²) worst case

SpaceO(n) recursion

Java

Try it out

class Solution {
    public int[] quickSort(int[] arr) {
        quickSortRange(arr, 0, arr.length - 1);
        return arr;
    }

    private void quickSortRange(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(arr, lo, hi);
        quickSortRange(arr, lo, p - 1);
        quickSortRange(arr, p + 1, hi);
    }

    private int partition(int[] arr, int lo, int hi) {
        int pivot = arr[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; 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[hi];
        arr[hi] = temp;
        return i + 1;
    }
}

Optimal — Middle-Element Pivot

Optimal

Exact same partition scheme — but before partitioning, swap the middle element of the current range to the end so IT becomes the pivot instead of whatever happens to already be there. On sorted or reverse-sorted input, the middle element is close to the true median, so each partition splits the range roughly in half instead of splitting off just one element. That keeps recursion depth around O(log n) instead of O(n), avoiding exactly the degenerate case the naive version falls into.

TimeO(n log n) expected

SpaceO(log n) expected recursion