Quick Sort

Partition + Recurse

1:00

How quick sort uses a pivot and in-place partition to sort an array in O(n log n) average time — and when it degrades to O(n²).

By the end, you can

Explain the pivot-partition-recurse structure of quick sort in plain language.
Trace a full Lomuto partition step on a small array and identify the pivot's final index.
Explain why the ≤ test in Lomuto sends equal elements to the left side and what that means for all-equal input.
State the average-case and worst-case time complexity, and identify which inputs trigger each.
Describe what "in-place" and "not stable" mean and how quick sort exemplifies both.
Compare the three pivot strategies (fixed end, random, median-of-three) and their effect on worst-case probability.
Contrast quick sort with merge sort on space, stability, and guaranteed time complexity.

Up next in Searching & Sorting