Sorting

package main

import "fmt"

// QuickSort function sorts an array in-place using left and right pointers
func QuickSort(arr []int, left, right int) {
    if left < right {
        pivotIndex := partition(arr, left, right)
        QuickSort(arr, left, pivotIndex-1)  // Sort left of pivot
        QuickSort(arr, pivotIndex+1, right) // Sort right of pivot
    }
}

// Partition function rearranges elements around the pivot
func partition(arr []int, left, right int) int {
    pivot := arr[right] // Choosing the last element as the pivot
    i := left           // Initialize i to start of the subarray
    
    for j := left; j < right; j++ { // Traverse the array
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j], arr[i] // Swap elements
            i++                             // Move the smaller-element pointer
        }
    }
    // Place pivot in its correct sorted position
    arr[i], arr[right] = arr[right], arr[i]
    return i // Return the pivot index
}

func main() {
    arr := []int{10, 7, 8, 9, 1, 5}
    fmt.Println("Original Array:", arr)
    QuickSort(arr, 0, len(arr)-1)
    fmt.Println("Sorted Array:", arr)
}