Problem Statement
Quick Sort
Quick Sort is a way to sort a list, and the trick behind it is "divide and conquer." That means: instead of sorting the whole list at once, you keep splitting it into smaller pieces until each piece is easy. Here is the picture. Imagine you are lining up kids by height. You grab one kid and call them the "pivot" (the chosen reference person). Then you tell everyone shorter than the pivot to stand on the left, and everyone taller to stand on the right. Now the pivot is in their exact final spot, and you have two smaller groups to sort the same way. Repeat on each group until everyone is in order. On average this takes O(n log n) time, which is fast. But if you keep picking a bad pivot (always the shortest or always the tallest person), it slows down to O(n squared). Picking the pivot at random fixes that in practice. Quick Sort also sorts the list in place, meaning it rearranges the same list instead of building a new one, so it uses very little extra memory, and it is usually faster than Merge Sort because it touches memory in a friendlier pattern.
Signals to notice
Brute force first
Not applicable — quicksort IS a sorting algorithm. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Choose pivot, partition: elements < pivot go left, > pivot go right. Recursively sort both sides. Average, worst with bad pivots. space for recursion stack. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on arr=[10, 7, 8, 9, 1, 5]
partition(0,5): pivot=arr[5]=5, i=-1; scan j=0..4, only arr[4]=1<5 -> i=0, swap -> [1,7,8,9,10,5] place pivot: swap arr[1],arr[5] -> [1,5,8,9,10,7]; return pi=1 left [0,0]=[1]: low>=high, base case (already sorted) partition(2,5): pivot=7, none<7 -> swap arr[2],arr[5] -> [1,5,7,9,10,8]; pi=2 partition(3,5): pivot=8, none<8 -> swap arr[3],arr[5] -> [1,5,7,8,10,9]; pi=3 partition(4,5): pivot=9, none<9 -> swap arr[4],arr[5] -> [1,5,7,8,9,10]; pi=4 all sub-ranges size<=1 -> return [1, 5, 7, 8, 9, 10]
What must stay true
After partitioning, the pivot is in its final sorted position. All elements left of it are smaller; all right are larger. Recursion handles the sub-arrays. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high) # pivot lands at final index pi
quickSort(arr, low, pi - 1) # sort left of pivot
quickSort(arr, pi + 1, high) # sort right of pivot
# partition: pivot=arr[high]; sweep j, swap arr[j]<pivot into i; place pivot at i+1Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Always choosing the first or last element as pivot — this gives on already-sorted input. Use random pivot or median-of-three for better average performance. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.