| 1 | package quick |
| 2 | |
| 3 | func sort(arr []int) []int { |
| 4 | var recurse func(left int, right int) |
| 5 | var partition func(left int, right int, pivot int) int |
| 6 | |
| 7 | partition = func(left int, right int, pivot int) int { |
| 8 | v := arr[pivot] |
| 9 | right-- |
| 10 | arr[pivot], arr[right] = arr[right], arr[pivot] |
| 11 | |
| 12 | for i := left; i < right; i++ { |
| 13 | if arr[i] <= v { |
| 14 | arr[i], arr[left] = arr[left], arr[i] |
| 15 | left++ |
| 16 | } |
| 17 | } |
| 18 | |
| 19 | arr[left], arr[right] = arr[right], arr[left] |
| 20 | return left |
| 21 | } |
| 22 | |
| 23 | recurse = func(left int, right int) { |
| 24 | if left < right { |
| 25 | pivot := (right + left) / 2 |
| 26 | pivot = partition(left, right, pivot) |
| 27 | recurse(left, pivot) |
| 28 | recurse(pivot+1, right) |
| 29 | } |
| 30 | } |
| 31 | |
| 32 | recurse(0, len(arr)) |
| 33 | return arr |
| 34 | } |