package cpu

func QuickSort(nums []int) {
	if len(nums) < 2 {
		return
	}
	quickSortHelper(nums, 0, len(nums)-1)
}

func quickSortHelper(nums []int, low, high int) {
	if low < high {
		pivotIndex := partition(nums, low, high)
		quickSortHelper(nums, low, pivotIndex-1)
		quickSortHelper(nums, pivotIndex+1, high)
	}
}

func partition(nums []int, low, high int) int {
	pivot := nums[high]
	i := low - 1

	for j := low; j < high; j++ {
		if nums[j] <= pivot {
			i++
			nums[i], nums[j] = nums[j], nums[i]
		}
	}

	nums[i+1], nums[high] = nums[high], nums[i+1]
	return i + 1
}