Quick Sort - Algorithm, Visualization, Examples

Problem Statement❯

Given an array of integers, your task is to sort the array in ascending order using the Quick Sort algorithm.

Quick Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
The process is applied recursively to the sub-arrays, resulting in a sorted array.

Examples❯

Input Array	Sorted Output	Description
[10, 5, 2, 3, 7]	[2, 3, 5, 7, 10]	Normal case with unsorted distinct integers
[5, 5, 5, 5]	[5, 5, 5, 5]	All elements are the same, already sorted
[9, 8, 7, 6, 5]	[5, 6, 7, 8, 9]	Reverse sorted input
[1]	[1]	Single-element array is already sorted
[]	[]	Empty array, nothing to sort
[3, -1, 0, 2]	[-1, 0, 2, 3]	Includes negative numbers
[100, 10, 1000, 1]	[1, 10, 100, 1000]	Wide range of values

Visualization Player

Solution❯

Quick Sort uses the divide-and-conquer technique. It selects a pivot and places it in the correct position, then recursively sorts the left and right subarrays. It's often faster than other simple sorting algorithms.

How We Approach the Problem

To sort an array using Quick Sort, we follow these steps:

Choose a pivot: Typically the last element of the current subarray.
Partition the array: Rearrange elements such that all values less than the pivot go to its left, and all values greater go to its right.
Recursively sort: Apply the same logic to the left and right subarrays.
Base case: When the subarray has 0 or 1 element, it's already sorted.

Let’s go through an example step-by-step:

Example: [8, 4, 7, 3, 10, 2]

Choose pivot = 2 (last element)
Partition: elements less than 2 go to left — none in this case. So 2 is swapped with 8. Now array becomes: [2, 4, 7, 3, 10, 8]
Now pivot index is 0. Left subarray: [] (empty), Right subarray: [4, 7, 3, 10, 8]
Repeat the process recursively on right subarray:
- Choose pivot = 8
- Partition left: [4, 7, 3], right: [10]
- Place pivot 8 at index 4
Repeat recursively on [4, 7, 3] → pivot = 3 → [3, 7, 4]
Eventually sorted array = [2, 3, 4, 7, 8, 10]

Case 1 - Normal Case with Mixed Elements

This is the typical case where the array has multiple unsorted elements.

Input: [6, 2, 8, 4, 10]
Steps:
1. Pivot = 10 → partitioned → [6, 2, 8, 4, 10]
2. Recursive calls on left part → pivot = 4 → sorted as [2, 4, 6, 8]
Output: [2, 4, 6, 8, 10]

Case 2 - Already Sorted Array

If the array is already sorted in ascending order, Quick Sort still works, but performance may degrade to O(n²) depending on pivot selection.

Input: [1, 2, 3, 4, 5]
Steps: Choosing last element as pivot causes left-heavy recursion.
Output: [1, 2, 3, 4, 5]

Case 3 - Reverse Sorted Array

This is a worst-case scenario for Quick Sort if the pivot is not selected smartly.

Input: [5, 4, 3, 2, 1]
Steps: Each pivot ends up being the smallest → O(n²) recursion.
Output: [1, 2, 3, 4, 5]

Case 4 - All Elements Equal

If all elements are equal, no real sorting is needed, but the algorithm still makes comparisons.

Input: [7, 7, 7, 7]
Steps: Partitioning doesn’t really change order, but recursion continues.
Output: [7, 7, 7, 7]

Case 5 - Single Element

A single element is trivially sorted.

Input: [3]
Steps: Base case — no sorting required.
Output: [3]

Case 6 - Empty Array

No elements to sort means the result is just an empty array.

Input: []
Steps: Base case hit immediately.
Output: []

Algorithm Steps❯

Select a pivot element from the array (commonly the last element).
Partition the array so that all elements less than the pivot are on its left, and all greater are on its right.
Recursively apply the same process to the subarrays on the left and right of the pivot.
Repeat until the base case is reached (subarray has one or no elements).
The array is now sorted in place without using additional memory.

Code

Python

Java

JavaScript

C++

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    quick_sort(arr)
    print("Sorted array is:", arr)

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n log n)	In the best case, the pivot divides the array into two equal halves at every step. This results in log n levels of recursion, with each level doing O(n) work for partitioning.
Average Case	O(n log n)	On average, the pivot splits the array into reasonably balanced parts. Each level of recursion requires O(n) operations, and there are log n such levels.
Worst Case	O(n^2)	In the worst case (e.g., when the pivot is always the smallest or largest element), the partition results in one subarray of size n−1 and one of size 0, leading to n levels of recursion and O(n) work per level.

Space Complexity❯

O(log n)

Explanation: The algorithm is in-place and does not use extra space for arrays, but the recursive calls use stack space. In the best/average case, the depth of the recursion is O(log n). In the worst case, it could be O(n) if not optimized with tail recursion.

⬅ Previous TopicMerge Sort

Next Topic ⮕Heap Sort