| K | V |
|---|---|
| Big O | O(log(n)) <-> O(n^2) |
| Space | O(1) |
1 This is a shortcut that effectively says, “swap p1 with p2”
2 Exit the recursive function once the array length is 1.
It is important to understand the foot-gun here. We are modifying the array 3 , not creating new ones. So while
the variables left and right look like new arrays, they are not. Modifying them modifies the top level array. This is
why space is O(1).
func (arr *Array[T]) QuickSort() { var s func(a *Array[T]) s = func(a *Array[T]) { if len(*a) < 2 { return } p1 := -1 p2 := 0 pivot := (*a)[len(*a)-1]
for p2 < len(*a)-1 { if Less((*a)[p2], pivot) { p1++ (*a)[p1], (*a)[p2] = (*a)[p2], (*a)[p1] } p2++ } p1++ (*a)[p1], (*a)[p2] = (*a)[p2], (*a)[p1]
left := (*a)[:p1] right := (*a)[p1+1:] if len(left) > 1 { s(&left) } if len(right) > 1 { s(&right) }} s(arr)}