Quick Sort
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 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.
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. The algorithm then recursively applies the same process to both sub-arrays. The partition step is the heart of Quick sort: a pointer scans from left to right, swapping elements smaller than the pivot to the front. When the scan completes, the pivot is swapped into its correct position.
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. Quick sort lacks stability, making it less ideal for multi-level sorting or cases where the original sequence of duplicate keys must be maintained.
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. |
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.