Quick Sort

1. Pick a pivot element p in the array
2. Partition the array into $<p|p|\ge p$
3. Recursively sort the two partitions.

Key benefit: No temporary array!

Pseudocode

def partition(ls, lo, hi):
	if lo < hi:
		pivot, i, j = ls[(lo + hi) // 2], lo, hi
		while True:
			while ls[i] < pivot and i < hi:
				i += 1
 
			while pivot < ls[j] and j > lo:
				j -= 1
 
			if i > j:
				break
 
			ls[i], ls[j] = ls[j], ls[i]
			i += 1
			j -= 1
 
		partition(ls, lo, j)
		partition(ls, i, hi)
		
def quicksort(ls):
	partition(ls, 0, len(ls) - 1)

Time Complexity

• Best Case: $O(n\log n)$
• Average Case: $O(n\log n)$
• Worst Case: $O(n^2)$

Space Complexity

• Worst Case: $O(\log n)$

Implementation details

1. How to pick a pivot?
   1. Random Element
   2. Median of three
2. Dealing with duplicates? Quicksort doesn’t perform well with lots of duplicate elemnts

CS240

See Partition.