Skip to main content

​
Overview

Quick Sort is one of the most efficient sorting algorithms in practice. It uses a divide-and-conquer strategy: select a “pivot” element, partition the array so elements smaller than the pivot are on the left and larger elements are on the right, then recursively sort the two partitions.

​
Complexity

  • Time Complexity:
    • Best case: O(n log n) - balanced partitions
    • Average case: O(n log n)
    • Worst case: O(n²) - already sorted or all elements equal (with bad pivot selection)
  • Space Complexity: O(log n) - due to recursion stack
  • Stable: No - may change relative order of equal elements

​
Implementation

Here’s the actual implementation from the Sorting Algorithms Visualiser: 
int partition(std::vector<int>& nums, int low, int high) {
	int pivot = nums[high];
	int i = (low - 1);
	for (int j = low; j < high; j++) {
		if (nums[j] <= pivot) {
			i++;
			HighlightRectangles(-1, i, j);
			swapNums(&nums[i], &nums[j]);
		}
		else {
			HighlightRectangles(-1, i, j);
		}
		std::this_thread::sleep_for(std::chrono::nanoseconds(SORT_DELAY));
	}
	swapNums(&nums[i + 1], &nums[high]);
	return (i + 1);
}

void QuickSort(std::vector<int>& nums, int low, int high) {
	if (low < high) {
		int partIndex = partition(nums, low, high);
		QuickSort(nums, low, partIndex - 1);
		QuickSort(nums, partIndex + 1, high);
	}
	return;
}

​
How It Works

​
The Partition Function

  1. Select Pivot: Choose the last element nums[high] as the pivot
  2. Initialize pointer: Set i = low - 1 (tracks the boundary of smaller elements)
  3. Scan array: Loop through elements from low to high - 1:
    • If nums[j] <= pivot: increment i, swap nums[i] and nums[j]
    • This moves elements ≤ pivot to the left side
  4. Place pivot: Swap pivot to its final position at i + 1
  5. Return: The pivot’s final index i + 1

​
The QuickSort Function

  1. Base case: If low >= high, the subarray has 0 or 1 element (already sorted)
  2. Partition: Call partition() to get the pivot’s final position
  3. Recursively sort:
    • Left subarray: elements before pivot (low to partIndex - 1)
    • Right subarray: elements after pivot (partIndex + 1 to high)

​
Step-by-Step Example

For the array [10, 7, 8, 9, 1, 5]: Initial Call: QuickSort(nums, 0, 5) First Partition (pivot = 5):
  • Scan: 1 is ≤ 5, move to left
  • Result: [1, 7, 8, 9, 10, 5] → swap pivot → [1, 5, 8, 9, 10, 7]
  • Pivot 5 is now at index 1
Recursive Calls:
  • Left: QuickSort(nums, 0, 0) → [1] already sorted
  • Right: QuickSort(nums, 2, 5) → Sort [8, 9, 10, 7]
Second Partition (pivot = 7):
  • Result: [1, 5, 7, 9, 10, 8]
Continue recursively until all subarrays are sorted:
  • Final: [1, 5, 7, 8, 9, 10]

​
Watch It in Action

When running the visualiser, you’ll see:
  • Green highlight (highlight2): The boundary pointer i (marks the end of elements ≤ pivot)
  • Blue highlight (highlight3): The current element j being examined
  • No red highlight: The implementation doesn’t use highlight1 in the partition function
During partitioning, you’ll see elements being compared to the pivot and swapped to the left side when they’re smaller. The recursive nature means you’ll see the algorithm working on smaller and smaller subarrays.
The visualization highlights show the partition boundary (green) and the current element being examined (blue) at lines 143 and 147. Watch how elements smaller than the pivot get swapped to the left side.

​
Pivot Selection

This implementation uses last element as pivot (nums[high]). This is simple but has drawbacks:
  • Best case: Pivot splits array roughly in half each time → O(n log n)
  • Worst case: Array already sorted or reverse sorted → pivot is always smallest/largest → O(n²)

​
Alternative Pivot Strategies:

  • First element: Same simplicity, same worst-case issue
  • Random element: Reduces chance of worst case
  • Median-of-three: Choose median of first, middle, and last elements
  • Median-of-medians: Guarantees good pivot but adds overhead

​
Best Use Cases

  • Large datasets: Excellent average-case performance
  • General-purpose sorting: Good default choice for most applications
  • In-memory sorting: Works well when data fits in memory
  • When average case matters more: O(n log n) on average

​
Advantages

✓ Fast average-case performance: O(n log n) ✓ In-place sorting (only O(log n) stack space) ✓ Cache-friendly (good locality of reference) ✓ Practical and widely used ✓ Easy to parallelize

​
Disadvantages

✗ Worst-case O(n²) time with poor pivot selection ✗ Not stable (equal elements may be reordered) ✗ Recursive - can cause stack overflow for large datasets ✗ Performance depends on pivot selection strategy
For already sorted or reverse sorted arrays, this implementation will exhibit O(n²) behavior because the pivot (last element) will always be the largest or smallest element. Consider using a randomized or median-of-three pivot selection for production code.

​
Optimizations

Common improvements to Quick Sort:
  1. Randomized pivot: Reduces worst-case probability
  2. Three-way partitioning: Efficient for arrays with many duplicates
  3. Insertion sort for small subarrays: Switch to Insertion Sort when subarray size < 10-20
  4. Tail recursion elimination: Reduce stack space usage
  5. Iterative implementation: Use explicit stack to avoid recursion overhead
Quick Sort is the algorithm of choice for many standard library implementations (like C++‘s std::sort uses a hybrid approach called “Introsort” that combines Quick Sort, Heap Sort, and Insertion Sort).

Build docs developers (and LLMs) love

Get started for freeTalk to us