How do I implement quick sort in Go?

Quick Sort is an efficient sorting algorithm that follows the divide-and-conquer principle. In Go, we can implement Quick Sort to perform sorting operations efficiently on arrays and slices.

Quick Sort is a popular sorting algorithm that is typically faster in practice than other \(O(n^2)\) algorithms, such as selection sort or bubble sort. It is a recursive algorithm that selects a 'pivot' element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
Keywords: Go, Quick Sort, Sorting Algorithm, Divide and Conquer, Recursive Algorithm

package main

import "fmt"

// quickSort function to sort an array
func quickSort(arr []int) []int {
    if len(arr) < 2 {
        return arr // Base case: arrays with 0 or 1 element are sorted
    }
    
    pivot := arr[0] // Choose the first element as the pivot
    var less []int // Define a slice for less than pivot
    var greater []int // Define a slice for greater than pivot

    // Partitioning the array
    for _, v := range arr[1:] {
        if v <= pivot {
            less = append(less, v)
        } else {
            greater = append(greater, v)
        }
    }
    
    // Recursively apply quickSort to the partitions and concatenate results
    return append(append(quickSort(less), pivot), quickSort(greater)...)
}

func main() {
    arr := []int{3, 6, 8, 10, 1, 2, 1}
    sortedArr := quickSort(arr)
    fmt.Println("Sorted array:", sortedArr)
}
    

Keywords: Go Quick Sort Sorting Algorithm Divide and Conquer Recursive Algorithm