Quick sort picks a pivot, partitions the array so all smaller elements are left of the pivot and all larger are right, then recursively sorts each partition. With a good pivot choice the work splits evenly at each level giving O(n log n) average time. It sorts in place so it is cache-friendly and fast in practice, which is why most standard library sort functions use it or a hybrid built around it.
Example: Sort 8 numbers using a pivot-based partition.
When to use this
→General-purpose in-place sorting — used inside Array.prototype.sort in most JS engines
→Cache-friendly sorting of large arrays where memory locality matters
→When average-case O(n log n) is acceptable and in-place is required
→Quickselect — the same partition logic finds the k-th smallest element in O(n) average
Quick sort picks a pivot element, partitions the array so everything smaller is left of the pivot and everything larger is right, then recursively sorts each side. Average case is O(n log n) with O(1) extra space.
Space play/pause← → stepR replay+ − speed
active line highlighted
1
defquick_sort(arr,lo=0,hi=None):
2
ifhiisNone:hi=len(arr)-1
3
iflo>=hi:return
4
pivot=arr[hi]
5
i=lo-1
6
forjinrange(lo,hi):
7
ifarr[j]<=pivot:
8
i+=1
9
arr[i],arr[j]=arr[j],arr[i]
10
arr[i+1],arr[hi]=arr[hi],arr[i+1]
11
p=i+1
12
quick_sort(arr,lo,p-1)
13
quick_sort(arr,p+1,hi)
Quick check
What is the worst-case time complexity of quick sort and when does it occur?
Why is quick sort often faster than merge sort in practice despite the same average complexity?