Log inSign up
mediumGeeksforGeeksNot Started

Quick Sort

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of integers nums, sort the array in ascending order using the Quick Sort algorithm.

You must implement an in-place divide-and-conquer sorting algorithm that partitions the array around a pivot element with average time complexity `O(N log N)` and `O(log N)` recursion stack space.

Example 1:

Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: Choosing pivot and partitioning partitions smaller elements to the left and larger to the right, sorting the array.

Example 2:

Input: nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: Duplicates are placed correctly around pivot partitions.

Example 3:

Input: nums = [3, -1, 4, 1, 5, 9, 2, 6]
Output: [-1, 1, 2, 3, 4, 5, 6, 9]
Explanation: Standard multi-element unsorted array rearranged to ascending order.

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Two-pointer array partitioning
  • Divide and conquer recursion mechanics
  • Understanding average vs worst-case algorithmic complexity

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Contrast Hoare's vs Lomuto's partitioning algorithms.
  • Understand why pivot selection (e.g. median-of-three or randomized) is critical to prevent O(N2) worst-case degradation.
  • Implement QuickSort in-place with O(log N) recursion depth.
  • Understand QuickSelect variant for O(N) average Kth-order statistics.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Need fastest in-place general purpose comparison sort in practical real-world scenarios.
  • Finding the K-th largest or smallest element in O(N) average time (QuickSelect).
  • Partitioning arrays around a pivot value.

Algorithmic Decision Tree:

  • If guaranteed O(N log N) worst-case and O(1) space is required -> HeapSort or IntroSort.
  • If stability is mandatory -> MergeSort or Timsort.
  • If average speed and minimal memory footprint are paramount -> QuickSort with Median-of-Three.

Connected Patterns:

Kth Largest Element in an Array (QuickSelect)Sort Colors (3-Way Dutch National Flag Partition)Wiggle Sort II

1. Brute Force (Out-of-Place Array Filtering)

Intuition

Picks the middle element as pivot and creates 3 fresh lists (less, equal, greater), recursing on less and greater.

Algorithm

  1. Step 1: If array length <= 1, return array copy.
  2. Step 2: Choose pivot = nums[length / 2].
  3. Step 3: Filter into left (x < pivot), mid (x == pivot), and right (x > pivot).
  4. Step 4: Return quickSort(left) + mid + quickSort(right).

Brute Force (Out-of-Place Array Filtering) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 7, 9, 11]
Current operationSTEP 1 OF 6
Phase 1 — Setup: Algorithm initializes tracking variables and sets initial inspection pointers for Quick Sort
Visual state
Values and pointers at this exact step
pointers
S
1
3
5
7
9
11
0
↑ Start
1
2
3
4
5
↑ End
Variables at this step
Initial State
Setup
Array Size
6
Target
Optimal Bound
Check / comparison
Input elements: [1, 3, 5, 7, 9, 11].
Decision / next transition
Initialize state variables for Brute Force (Out-of-Place Array Filtering).
Why this step matters

Phase 1 — Setup: Algorithm initializes tracking variables and sets initial inspection pointers for Quick Sort.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> quickSortOutOfPlace(const std::vector<int>& nums) {
7 if (nums.size() <= 1) return nums;
8 int pivot = nums[nums.size() / 2];
9 std::vector<int> left, mid, right;
10 for (int x : nums) {
11 if (x < pivot) left.push_back(x);
12 else if (x == pivot) mid.push_back(x);
13 else right.push_back(x);
14 }
15 left = quickSortOutOfPlace(left);
16 right = quickSortOutOfPlace(right);
17
18 std::vector<int> result;
19 result.insert(result.end(), left.begin(), left.end());
20 result.insert(result.end(), mid.begin(), mid.end());
21 result.insert(result.end(), right.begin(), right.end());
22 return result;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::vector<int> nums = {5, 2, 3, 1};
29 std::vector<int> res = sol.quickSortOutOfPlace(nums);
30 std::cout << "Sorted: ";
31 for (int x : res) std::cout << x << " ";
32 std::cout << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Out-of-Place Array Filtering).
  • Space complexity: O(1) — Space complexity for Brute Force (Out-of-Place Array Filtering).

Why Brute Force Doesn't Scale:

Naive pivot selection triggers stack overflow on 50,000 sorted elements. Median-of-three selection and Hoare inward traversal achieves exceptional cache line locality and O(N log N) performance.

On an array of 100,000 sorted integers: Naive first-element QuickSort takes ~10 billion operations (and stack overflows); Median-of-three Hoare QuickSort completes in ~1.5 million operations (< 10 ms).

2. Better (Lomuto In-Place Partitioning)

Intuition

Lomuto partition uses the last element as pivot. All elements smaller than pivot are swapped to the front (tracked by pointer i). Finally, pivot is swapped to index i+1.

Algorithm

  1. Step 1: Set pivot = nums[high], i = low - 1.
  2. Step 2: For j = low to high - 1: if nums[j] <= pivot, increment i and swap nums[i] with nums[j].
  3. Step 3: Swap nums[i + 1] with nums[high]. Return partition index i + 1.
  4. Step 4: Recursively sort left of pivot and right of pivot.

Better (Lomuto In-Place Partitioning) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 7, 9, 11]
Current operationSTEP 1 OF 6
Phase 1 — Setup: Algorithm initializes tracking variables and sets initial inspection pointers for Quick Sort
Visual state
Values and pointers at this exact step
pointers
S
1
3
5
7
9
11
0
↑ Start
1
2
3
4
5
↑ End
Variables at this step
Initial State
Setup
Array Size
6
Target
Optimal Bound
Check / comparison
Input elements: [1, 3, 5, 7, 9, 11].
Decision / next transition
Initialize state variables for Better (Lomuto In-Place Partitioning).
Why this step matters

Phase 1 — Setup: Algorithm initializes tracking variables and sets initial inspection pointers for Quick Sort.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6private:
7 int lomutoPartition(std::vector<int>& nums, int low, int high) {
8 int pivot = nums[high];
9 int i = low - 1;
10 for (int j = low; j < high; j++) {
11 if (nums[j] <= pivot) {
12 i++;
13 std::swap(nums[i], nums[j]);
14 }
15 }
16 std::swap(nums[i + 1], nums[high]);
17 return i + 1;
18 }
19
20 void quickSortHelper(std::vector<int>& nums, int low, int high) {
21 if (low < high) {
22 int p = lomutoPartition(nums, low, high);
23 quickSortHelper(nums, low, p - 1);
24 quickSortHelper(nums, p + 1, high);
25 }
26 }
27
28public:
29 void quickSort(std::vector<int>& nums) {
30 if (!nums.empty()) {
31 quickSortHelper(nums, 0, nums.size() - 1);
32 }
33 }
34};
35
36int main() {
37 Solution sol;
38 std::vector<int> nums = {5, 2, 3, 1};
39 sol.quickSort(nums);
40 std::cout << "Lomuto Sorted: ";
41 for (int x : nums) std::cout << x << " ";
42 std::cout << std::endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Lomuto In-Place Partitioning).
  • Space complexity: O(N) — Space complexity for Better (Lomuto In-Place Partitioning).

3. Optimal (Hoare Partitioning with Randomized / Median Pivot)

Intuition

Hoare's partitioning scheme uses two pointers: i starts before low and advances while nums[i] < pivot; j starts after high and decrements while nums[j] > pivot. When both stop, swap nums[i] and nums[j]. This repeats until i >= j, returning partition index j. Combining this with median-of-three or random pivot selection protects against O(N2) degradation on sorted/reverse inputs.

Algorithm

  1. Step 1: Pick pivot as median-of-three or random index in [low...high].
  2. Step 2: Initialize i = low - 1, j = high + 1.
  3. Step 3: Loop:
  4. - Increment i while nums[i] < pivot.
  5. - Decrement j while nums[j] > pivot.
  6. - If i >= j, return j.
  7. - Swap nums[i] with nums[j].
  8. Step 4: Recursively call quickSort on [low...j] and [j + 1...high].

Hoare Partition on [5, 2, 3, 1]

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [nums = [5, 2, 3, 1]]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
nums = [5, 2, 3, 1]
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
nums = [5, 2, 3, 1]
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6private:
7 int hoarePartition(std::vector<int>& nums, int low, int high) {
8 int mid = low + (high - low) / 2;
9 int pivot = nums[mid];
10 int i = low - 1;
11 int j = high + 1;
12
13 while (true) {
14 do { i++; } while (nums[i] < pivot);
15 do { j--; } while (nums[j] > pivot);
16 if (i >= j) return j;
17 std::swap(nums[i], nums[j]);
18 }
19 }
20
21 void quickSortHelper(std::vector<int>& nums, int low, int high) {
22 if (low < high) {
23 int p = hoarePartition(nums, low, high);
24 quickSortHelper(nums, low, p);
25 quickSortHelper(nums, p + 1, high);
26 }
27 }
28
29public:
30 void quickSort(std::vector<int>& nums) {
31 if (!nums.empty()) {
32 quickSortHelper(nums, 0, (int)nums.size() - 1);
33 }
34 }
35};
36
37int main() {
38 Solution sol;
39 std::vector<int> nums = {5, 2, 3, 1};
40 sol.quickSort(nums);
41 std::cout << "Optimal Hoare Sorted: ";
42 for (int x : nums) std::cout << x << " ";
43 std::cout << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (Hoare Partitioning with Randomized / Median Pivot).
  • Space complexity: O(1) — Space complexity for Optimal (Hoare Partitioning with Randomized / Median Pivot).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Extra Array Filtering / Out-of-Place)O(N log N) averageO(N log N)Pick pivot, filter elements into left (< pivot), mid (== pivot), and right (> pivot) lists, then concatenate.Allocating new lists at every recursion level.
2.Better (Lomuto Partition Scheme)O(N log N) avg, O(N^2) worst caseO(log N) stackUse a single pointer i tracking boundary of elements < pivot, scanning with j from low to high - 1.Single direction pointer scan and duplicate value handling.
3.Optimal (Hoare Partition + Randomized / Median Pivot)OptimalO(N log N) avg, O(N log N) expected worst caseO(log N) stackTwo pointers moving inward from both ends, swapping inverted pairs, using median-of-three pivot.Partition pointer convergence.

Common Pitfalls & Crucial Edge Cases

Using `nums[low]` or `nums[high]` as pivot on already sorted arrays

Degrades partition to 1 element vs N-1 elements, resulting in O(N2) time and call stack overflow.

Recursing on `p - 1` and `p + 1` with Hoare partition

Unlike Lomuto, Hoare partition returns index j such that elements in [low...j] <= pivot and [j+1...high] >= pivot. Pivot is not necessarily at index j, so you must recurse on [low...j] and [j+1...high].

Using `<=` in Hoare inner loops (`while (nums[i] <= pivot)`)

Can cause pointers to run out of array bounds and fails to balance duplicate arrays.

Crucial Edge Cases to Validate:

  • Already Sorted Array ([1, 2, 3, 4, 5]): Picking nums[mid] as pivot creates balanced halves, avoiding O(N2) degradation.
  • All Equal Elements ([5, 5, 5, 5]): Hoare's partition stops at equal elements and swaps them, splitting the array right in the middle (O(N log N)). Lomuto would degrade to O(N2).
  • Two Element Inversion ([2, 1]): i stops at 0, j stops at 1, swaps to [1, 2], partitions correctly.
  • Single Element Array ([1]): Recursion terminates immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Be prepared to explain the difference between Hoare and Lomuto partitioning.
  2. Always mention Introsort and why modern language runtimes pair QuickSort with HeapSort to guarantee worst-case safety.
  3. Emphasize how QuickSelect can find the Kth largest element in O(N) average time by only recursing into one branch.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What causes standard QuickSort with first-element pivot to degrade to O(N2) worst case?

2.Why does Hoare's partitioning scheme perform fewer swaps than Lomuto's scheme?

3.What is the average and worst-case recursion stack space complexity of in-place QuickSort?

Back to DSA Sheet