Go Program for Quick Sort Algorithm with Example

A Go program for quick sort uses a recursive function that picks a pivot, partitions the slice around it, and sorts the parts with func quickSort(arr []int) []int.

Examples

Input[3, 1, 4, 1, 5]

Output[1 1 3 4 5]

Input[10, 7, 8, 9, 1, 5]

Output[1 5 7 8 9 10]

Input[]

Output[]

How to Think About It

To sort a list using quick sort, pick a pivot element and divide the list into two parts: elements less than the pivot and elements greater than or equal to the pivot. Then, sort each part by repeating the same steps until the list is fully sorted.

Algorithm

1

If the list has 0 or 1 element, return it as it is already sorted.

2

Choose the last element as the pivot.

3

Create two lists: one for elements less than the pivot, one for elements greater or equal.

4

Recursively quick sort both lists.

5

Combine the sorted left list, pivot, and sorted right list into one sorted list.

6

Return the combined sorted list.

Code

go

package main

import "fmt"

func quickSort(arr []int) []int {
    if len(arr) < 2 {
        return arr
    }
    pivot := arr[len(arr)-1]
    var left, right []int
    for _, v := range arr[:len(arr)-1] {
        if v < pivot {
            left = append(left, v)
        } else {
            right = append(right, v)
        }
    }
    left = quickSort(left)
    right = quickSort(right)
    return append(append(left, pivot), right...)
}

func main() {
    arr := []int{10, 7, 8, 9, 1, 5}
    sorted := quickSort(arr)
    fmt.Println(sorted)
}

Output

[1 5 7 8 9 10]

Dry Run

Let's trace the array [10, 7, 8, 9, 1, 5] through the quickSort function.

1

Initial call

arr = [10, 7, 8, 9, 1, 5], pivot = 5

2

Partition

left = [1], right = [10, 7, 8, 9]

3

Recursive call on left

quickSort([1]) returns [1]

4

Recursive call on right

quickSort([10, 7, 8, 9]) with pivot=9

5

Partition right

left = [7, 8], right = [10]

6

Recursive calls on right's parts

quickSort([7, 8]) returns [7, 8], quickSort([10]) returns [10]

7

Combine right parts

[7, 8] + [9] + [10] = [7, 8, 9, 10]

8

Combine all

[1] + [5] + [7, 8, 9, 10] = [1, 5, 7, 8, 9, 10]

Call	Array	Pivot	Left	Right	Result
1	[10,7,8,9,1,5]	5	[1]	[10,7,8,9]	pending
2	[1]	1	[]	[]	[1]
3	[10,7,8,9]	9	[7,8]	[10]	pending
4	[7,8]	8	[7]	[]	[7,8]
5	[10]	10	[]	[]	[10]
6	combine right				[7,8,9,10]
7	combine all				[1,5,7,8,9,10]

Why This Works

Step 1: Choosing a pivot

The pivot divides the array into smaller parts to sort separately, making sorting easier.

Step 2: Partitioning

Elements less than the pivot go to one side, others to the other side, organizing the array around the pivot.

Step 3: Recursion

Sorting the smaller parts recursively breaks the problem into simpler tasks until fully sorted.

Alternative Approaches

In-place Quick Sort

go

package main

import "fmt"

func quickSortInPlace(arr []int, low, high int) {
    if low < high {
        p := partition(arr, low, high)
        quickSortInPlace(arr, low, p-1)
        quickSortInPlace(arr, p+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    arr[i], arr[high] = arr[high], arr[i]
    return i
}

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

This version sorts the array without extra slices, saving memory but is more complex.

Using channels for concurrency

go

package main

import (
    "fmt"
)

func quickSortConcurrent(arr []int) []int {
    if len(arr) < 2 {
        return arr
    }
    pivot := arr[len(arr)-1]
    var left, right []int
    for _, v := range arr[:len(arr)-1] {
        if v < pivot {
            left = append(left, v)
        } else {
            right = append(right, v)
        }
    }
    leftChan := make(chan []int)
    rightChan := make(chan []int)
    go func() { leftChan <- quickSortConcurrent(left) }()
    go func() { rightChan <- quickSortConcurrent(right) }()
    leftSorted := <-leftChan
    rightSorted := <-rightChan
    return append(append(leftSorted, pivot), rightSorted...)
}

func main() {
    arr := []int{10, 7, 8, 9, 1, 5}
    sorted := quickSortConcurrent(arr)
    fmt.Println(sorted)
}

This approach uses Go routines to sort parts concurrently, improving speed on large data but adds complexity.

Complexity: O(n log n) average, O(n^2) worst case time, O(log n) average due to recursion stack, O(n) if not in-place space

Time Complexity

Quick sort divides the array and sorts parts recursively. Average case is O(n log n) because it splits roughly in half each time. Worst case is O(n^2) when pivot divides poorly.

Space Complexity

Extra space is used for recursion stack and temporary slices. In-place versions reduce space to O(log n) for recursion.

Which Approach is Fastest?

In-place quick sort is fastest in practice due to less memory use. Concurrent quick sort can be faster on large data with multiple CPU cores.

Approach	Time	Space	Best For
Simple recursive with slices	O(n log n) avg	O(n)	Easy to understand, small data
In-place quick sort	O(n log n) avg	O(log n)	Memory efficient, large data
Concurrent quick sort	Faster on multi-core	O(n)	Large data, parallel processing