Overview
Quick Sort is a divide-and-conquer algorithm that picks a 'pivot', partitions the array so smaller elements go left and larger go right, then recursively sorts each side. It is the default in-memory sort in many standard libraries.
How Quick Sort works
- Choose a pivot element from the current range.
- Partition: rearrange so all values less than the pivot precede it and all greater follow it.
- The pivot is now in its final sorted position.
- Recursively apply the same steps to the left and right sub-ranges.
When to use it
- General-purpose in-memory sorting where average speed matters most.
- When in-place sorting is needed — it uses only O(log n) stack space.
- Prefer Merge Sort when guaranteed O(n log n) worst-case or stability is required.
Complexity analysis
With balanced partitions Quick Sort runs in O(n log n) on average. A poor pivot on already-sorted data can degrade it to O(n²); randomised or median-of-three pivots make that rare. It sorts in place and is not stable.
Frequently asked questions
Why can Quick Sort be O(n²) in the worst case?
If the pivot is always the smallest or largest element, partitions become maximally unbalanced (size n−1 and 0), producing n levels of O(n) work. Randomising the pivot avoids this in practice.
Quick Sort vs Merge Sort — which should I use?
Quick Sort is usually faster in practice and sorts in place; Merge Sort guarantees O(n log n) and is stable but needs O(n) extra memory. Choose based on worst-case guarantees and stability needs.