Can Quick Sort handle duplicate values?

Yes. Duplicate values can be placed on either side of the pivot depending on the partition rule. The shown Lomuto partition places values no greater than the pivot on the left side.

Can Quick Sort sort negative values?

Yes. Quick Sort only compares values, so negative numbers, zero, and positive numbers are handled by the same partition logic.

How can worst-case time be reduced?

Random pivot selection, middle pivot selection, median-of-three pivot selection, and introspective sorting reduce the chance of repeatedly unbalanced partitions.

Is Quick Sort always better than Merge Sort?

No. Quick Sort usually uses less auxiliary storage with in-place partitioning, while Merge Sort gives guaranteed O(n log n) time and stable ordering in common implementations.

Quick Sort Algorithm: Partitioning and Time Complexity

Q: Is Quick Sort stable?

No. Standard in-place Quick Sort swaps values across the array during partitioning, so equal values can change relative order.

An integer array arr is given. Rearrange all values in non-decreasing order by applying the Quick Sort algorithm.

During every partition step, one pivot value must be selected and placed at the correct sorted position. Values smaller than or equal to the pivot are moved toward the left side, and greater values are moved toward the right side. Return the sorted array.

Example 1

Input: arr = [10, 7, 8, 9, 1, 5]
Output: [1, 5, 7, 8, 9, 10]
Explanation: Pivot-based partitioning places value 5 first. Smaller values move left, greater values move right, and the same sorting process continues on both sides.

Example 2

Input: arr = [4]
Output: [4]
Explanation: A single value already occupies the correct sorted position, so no partition step is required.

Practice it by yourself before moving onto the solutionTry now

Approach

A pivot is chosen to split the array into two smaller parts. Values smaller than the pivot are moved to its left, while larger values remain on its right.

A boundary index helps build the smaller-value region during the scan. After placing the pivot between the two regions, its position becomes fixed.

The same process is then repeated on the left and right parts. Each step breaks the array into smaller sections until every section has at most one element and is already sorted.

Algorithm

Start with the range 0 to n - 1 because it represents the complete array that needs to be sorted.
Process a range only when low < high because an empty or single-value range is already sorted.
Choose the last value as the pivot because it gives the scan one fixed value for comparison.
Start the boundary before the range because the smaller-value region is empty at the beginning.
Scan from low to high - 1 because the pivot at high should remain unchanged during comparison.
Move values no greater than the pivot into the left region so smaller values stay together.
Place the pivot just after the left region because that is its correct sorted position.
Repeat the process on both sides of the pivot because only those parts still need sorting.

Dry Run

Quick Sort

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    // Sorts an integer array with in-place Quick Sort.
7    vector<int> quickSort(vector<int>& arr) {
8        int n = arr.size();
9        solve(arr, 0, n - 1);
10        return arr;
11    }
12
13private:
14    // Sorts the current index range recursively.
15    void solve(vector<int>& arr, int low, int high) {
16        // Empty and single-value ranges are already sorted.
17        if (low >= high) {
18            return;
19        }
20
21     // Split the range into smaller and greater sides using the pivot.
22        int pivotIndex = partitionArray(arr, low, high);
23
24        // Values before the pivot are sorted independently.
25        solve(arr, low, pivotIndex - 1);
26
27        // Values after the pivot are sorted independently.
28        solve(arr, pivotIndex + 1, high);
29    }
30
31    // Places the pivot in the final sorted position.
32    int partitionArray(vector<int>& arr, int low, int high) {
33        int pivot = arr[high];
34        int smallerIndex = low - 1;
35
36        // Every scanned value is compared with the pivot once.
37        for (int current = low; current < high; current++) {
38            // Values no greater than the pivot belong in the left region.
39            if (arr[current] <= pivot) {
40                smallerIndex++;
41                swap(arr[smallerIndex], arr[current]);
42            }
43        }
44
45        // The pivot is placed directly after the left region.
46        swap(arr[smallerIndex + 1], arr[high]);
47        return smallerIndex + 1;
48    }
49};
50
51// Driver code
52int main() {
53    // Input array
54    vector<int> arr = {10, 7, 8, 9, 1, 5};
55
56    // Solution object creation
57    Solution obj;
58
59    // Result printing
60    vector<int> answer = obj.quickSort(arr);
61    for (int value : answer) {
62        cout << value << " ";
63    }
64
65    return 0;
66}

Note: Direct recursion may fail for large input values. Repeated unbalanced subproblems create quadratic work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(N log N) on average because each partition scans the active range once, and balanced partitions create about log N levels. The worst-case time complexity is O(N²) when the selected pivot is repeatedly the smallest or largest value.

Space Complexity: O(log N) on average because balanced recursion keeps about log N active calls on the stack. The worst-case recursion stack space is O(N) when partitions become completely unbalanced. No extra array proportional to N is created during partitioning.

Interview follow-up Questions