Python Tutorial
Quick Sort
A fast divide-and-conquer sort that partitions around a pivot and recurses on each side.
The Partition Strategy
Quicksort picks a pivot, then partitions the array so everything smaller than the pivot goes left and everything larger goes right. The pivot is now in its final position. It recurses on the two halves. Average time is O(n log n), and it sorts in place with low overhead — often the fastest general sort in practice.
Readable Version
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + mid + quick_sort(right)
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# [1, 1, 2, 3, 6, 8, 10]This version is easy to read but uses extra memory. The classic in-place version partitions within the array.
In-Place (Lomuto Partition)
def quick_sort_inplace(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
p = partition(arr, low, high)
quick_sort_inplace(arr, low, p - 1)
quick_sort_inplace(arr, p + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high] # choose last element as pivot
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1 # pivot's final index
print(quick_sort_inplace([10, 7, 8, 9, 1, 5]))
# [1, 5, 7, 8, 9, 10]Complexity and Pivot Choice
| Case | Time | When |
|---|---|---|
| Best / Average | O(n log n) | Balanced partitions |
| Worst | O(n²) | Pivot is always min/max (e.g. sorted input with last-element pivot) |
| Space | O(log n) | Recursion stack |
A fixed pivot triggers the O(n²) worst case on already-sorted data. Choose a random pivot or the median-of-three to make that case astronomically unlikely.
import random
def partition_random(arr, low, high):
r = random.randint(low, high)
arr[r], arr[high] = arr[high], arr[r] # randomize pivot
return partition(arr, low, high)Quick Sort vs Merge Sort
- Quicksort: in-place, cache-friendly, usually fastest — but O(n²) worst case and not stable.
- Merge sort: guaranteed O(n log n) and stable, but needs O(n) extra memory.
Best Practices
- Randomize or use median-of-three pivots to avoid the worst case.
- Switch to insertion sort for small subarrays to reduce overhead.
- Use quickselect (partition without full recursion) to find the k-th smallest in O(n) average.
- In real code just call
sorted()— CPython's Timsort is stable and highly optimized.
Try It Yourself
Exercise 1: What input triggers quicksort's O(n²) worst case with a fixed last-element pivot?
Show solution
Already-sorted (or reverse-sorted) data — every partition is maximally unbalanced. Randomizing the pivot avoids this.
Exercise 2: Is quicksort stable?
Show solution
No — partitioning can reorder equal elements. Use merge sort or Timsort when stability matters.
📘 Real-World Deep Dive
Knowing <strong>DSA Quick Sort (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Quick Sort that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
def qsort(xs):
if len(xs) <= 1: return xs
pivot = xs[len(xs)//2]
less = [x for x in xs if x < pivot]
equal = [x for x in xs if x == pivot]
more = [x for x in xs if x > pivot]
return qsort(less) + equal + qsort(more)
print(qsort([29, 10, 14, 37, 13, 8, 25]))Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Quick Sort as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.