DSA — Sorting Algorithms

Quick Sort

Choose pivot, partition array so smaller elements go left and larger go right, then recurse on both sides.

— min read
O(n log n)Average
O(n²)Worst
O(log n)Space
PivotSelection
UnstableIn-place
// QUICK SORT — LIVE ANIMATION
Speed
Press ▶ Sort to begin
How It Works
Python Code
Complexity
Quiz
Practice
01
Choose Pivot
Last element as pivot (or randomize for safety).
pivot = arr[high]
02
Partition
Move elements < pivot to the left.
i = lo-1; for j in range(lo,high)
03
Place Pivot
Swap pivot to its final sorted position.
arr[i+1], arr[high] = arr[high], arr[i+1]
04
Recurse
Sort left and right sub-arrays independently.
quicksort(lo, pi-1); quicksort(pi+1, hi)
python 
def quicksort(arr, lo, hi):
    if lo < hi:
        pi = partition(arr, lo, hi)
        quicksort(arr, lo, pi-1)
        quicksort(arr, pi+1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]; i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1
O(n log n)
Average
Random/shuffled data
O(n²)
Worst Case
Already sorted + bad pivot
O(log n)
Stack Space
Recursive call depth
Fastest
In Practice
Best cache performance, low constants
What causes Quick Sort's worst-case O(n²)?
Progress 0 / 5 solved
5 problems · 3 PBC · 2 Startup
#1801 Kth Largest Element in Array Google, Meta PBC →
#1802 Sort Colors (Dutch Flag) Amazon, Microsoft PBC →
#1803 Wiggle Sort II Google PBC →
#1804 Partition Array by Odd Even Razorpay STARTUP →
#1805 Minimum Operations to Sort Array Cogoport STARTUP →
← Merge Sort