// 1. Select a pivot element (can choose the first element or random element)
// 2. Use two pointers starting from both ends, right pointer moves first
// 3. Right pointer stops when finding element smaller than pivot
// 4. Left pointer then moves and stops when finding element larger than pivot
// 5. Swap elements found in steps 3 & 4
// 6. Repeat 3-5 until pointers meet
// 7. When pointers collide, perform final swap to ensure correctness
func quickSort(data []int, left, right int) {
    if left >= right {
        return
    }
    
    pivotIndex := partition(data, left, right)
    
    quickSort(data, left, pivotIndex-1)
    quickSort(data, pivotIndex+1, right)
}

func partition(data []int, left, right int) int {
    pivotIndex := left
    pivot := data[pivotIndex]
    
    for left != right {
        // Right pointer moves first
        if data[right] > pivot {
            right--
            continue
        }
        
        // Left pointer moves only when <= pivot 
        // (prevents infinite loop with equal elements)
        if data[left] <= pivot {
            left++
            continue
        }
        
        // Swap mismatched pairs
        data[left], data[right] = data[right], data[left]
    }
    
    // Final swap to place pivot in correct position
    data[left], data[pivotIndex] = data[pivotIndex], data[left]
    
    return left
}