Mathematical analysis of **quicksort** shows that, on average, the **algorithm** takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n^{2}) comparisons, though this behavior is rare.

## Golang

```
import (
"math/rand"
)
func quicksort(a []int) []int {
if len(a) < 2 {
return a
}
left, right := 0, len(a)-1
pivot := rand.Int() % len(a)
a[pivot], a[right] = a[right], a[pivot]
for i, _ := range a {
if a[i] < a[right] {
a[left], a[i] = a[i], a[left]
left++
}
}
a[left], a[right] = a[right], a[left]
quicksort(a[:left])
quicksort(a[left+1:])
return a
}
func sortedSquares(A []int) []int {
for i := 0; i < len(A); i++ {
n := A[i] * A[i]
A[i] = n
}
A = quicksort(A)
return A
}
```