Quick Sort Visualization
Quick Sort is the speedster of sorting algorithms. It picks a "pivot" element and then arranges the rest of the elements into two groups: those less than the pivot and those greater. By recursively sorting these groups, Quick Sort efficiently sorts even the largest datasets. It is a perfect blend of strategy and speed, making it one of the most popular sorting techniques. However, its performance can degrade in certain cases, unlike the guaranteed O(n log n) of Merge Sort.
This visualization uses the Hoare partition scheme with two converging pointers starting from opposite ends. The left pointer moves right until it finds an element larger than the pivot, while the right pointer moves left until it finds a smaller element. When both find misplaced elements, they swap them and continue until the pointers cross.
Pseudocode
function partition(start, end):
pivot = arr[end]
i = start, j = end - 1
while i < j:
if arr[i] <= pivot:
i = i + 1
else if arr[j] > pivot:
j = j - 1
else: swap(i, j)
if arr[i] > pivot: swap(i, end)
Visualizer
function quickSort(start, end):
if start < end:
pivot = partition(start, end)
quickSort(start, pivot - 1)
quickSort(pivot + 1, end)
Select number of elements:
How It Works
Quick sort selects a pivot element from the array (commonly the last element). It then partitions the remaining elements into two sub-arrays — elements less than the pivot go to the left, and elements greater go to the right. Once partitioning is complete, the array is divided into two distinct sub-arrays. Quick Sort then recursively calls itself on both sub-arrays, repeating the pivot selection and pointer partitioning steps until each sub-array shrinks to a single element or becomes empty, resulting in a fully sorted array.
When to Use
Quick sort is the go-to algorithm in many standard library implementations (including C's qsort) because of its excellent average-case performance and cache efficiency. It is preferred when average-case speed matters more than worst-case guarantees. However, randomized pivot selection or median-of-three strategies can mitigate the worst-case scenario.
Time & Space Complexity
Metric / Operation | Complexity | Description |
|---|---|---|
| Best Case | O(n log n) | When the pivot consistently divides the array into two roughly equal halves. |
| Average Case | O(n log n) | Random input distributions tend to produce balanced partitions. |
| Worst Case | O(n²) | Occurs when the pivot is always the smallest or largest element (e.g. already sorted input with last-element pivot). |
| Space Complexity | O(log n) | While Quick sort is in-place, the recursive call stack uses O(log n) space on average, or O(n) in the worst case. |
Common Interview Questions
What causes Quick Sort's O(n²) worst-case time complexity?
The worst-case occurs when the pivot chosen is consistently the smallest or largest element (e.g. picking first or last element on sorted or reverse-sorted data), resulting in highly unbalanced partitions.
Compare Hoare's partitioning scheme with Lomuto's partitioning scheme.
Lomuto uses one direction scan, makes 3x more swaps on average, and degrades to O(n²) when all elements are equal. Hoare uses two converging pointers from both ends, makes far fewer swaps, and efficiently handles duplicate element arrays.
How Quick Sort handle arrays with many duplicate elements?
Standard Quick Sort can perform poorly when many duplicate elements are present because they may lead to unbalanced partitions and unnecessary recursive calls. Three-way partitioning improves performance by grouping equal elements together, reducing recursion on duplicate values.
Why is Quick Sort often faster than Merge Sort in practice?
Quick Sort generally performs better due to better cache locality (working in-place on contiguous memory) and smaller constant factors in its operations (fewer data movements compared to Merge Sort’s copying to temporary arrays).
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0