Overview
Quick Sort chooses a pivot, rearranges the array so smaller values are on one side and larger values are on the other, then recursively sorts the partitions.
FoundationSource checked
Quick Sort
Sorts a list by partitioning values around a pivot and recursively sorting each side.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Intermediate
- Family
- Divide and Conquer
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Quicksort
Core Concepts
partitioningpivot selectiondivide and conquerin-place sorting
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n^2)
Space
O(log n)
When to Use
- Use it for fast in-place sorting on arrays.
- Use it when average-case speed and cache locality matter.
- Use randomized or median-style pivots when input order may be adversarial.
When Not to Use
- Avoid naive pivot choices when inputs may already be sorted or adversarial.
- Avoid it when stable ordering is required unless using a specialized stable variant.
- Avoid deep recursion without a guard or fallback.
What It Does
- Partitions data around a pivot
- Recursively sorts each side
Use Cases
- Fast in-memory sorting
- Sorting arrays
- Teaching partition-based algorithms
Inputs
- Array or list of comparable values
Outputs
- Sorted array or list
Pseudocode
- 1.Choose a pivot value
- 2.Partition the list into values below and above the pivot
- 3.Recursively quick sort the left partition
- 4.Recursively quick sort the right partition
- 5.Stop when a partition has fewer than two items
Canonical Example
- Input
- array = [3, 1, 4, 2], pivot = 3
- Output
- [1, 2, 3, 4]
- Explanation
- Partitioning places values below 3 before the pivot and values above 3 after it, then sorts both sides.
Implementation Notes
- Partition ranges with clear inclusive or half-open bounds.
- Use randomized, median-of-three, or introsort-style fallback strategies for robustness.
- Handle duplicate-heavy inputs with a three-way partition when appropriate.
Common Pitfalls
- Choosing a pivot strategy that creates highly unbalanced partitions.
- Mishandling equal keys and recursing over the same range again.
- Using recursive calls without limiting stack depth on large inputs.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow a pivot and values moving to the correct side of it.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Choose a pivot value
array-partitionNotes
Quick sort is usually fast in memory, but its worst case is avoided through pivot strategy and implementation safeguards.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Quick Sort invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesHeap Sort
Sorting · Foundation
Heap Sort avoids Quick Sort's worst-case partition behavior but is usually less cache-friendly.
Compare with thisAlternative toMerge Sort
Sorting · Foundation
Quick Sort partitions in place, while Merge Sort merges sorted subarrays.
Compare with thisRelationships
View full relationship pageAlternative toMerge Sort
Quick Sort partitions in place, while Merge Sort merges sorted subarrays.
Prerequisite ofQuickselect
Quickselect adapts Quick Sort partitioning to select one order statistic.
Related Algorithms
Tags
Comparison SortDivide and ConquerIn PlaceRecursion