Golang DSA Chapter 8 Part 1: Sorting Algorithms in Go

Chapter 8 of “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi is called “Classic Algorithms.” It covers sorting, searching, recursion, and hashing. That’s a lot of ground, so we’re splitting it into two parts. This first part is all about sorting.

Sorting is one of those things that sounds simple until you realize there are dozens of ways to do it, each with different trade-offs. The book walks through six sorting algorithms, and we’ll cover all of them here with Go code.

Quick context on how sorting algorithms get judged: computational complexity (how fast), memory usage (how much extra space), stability (do equal elements keep their original order), and whether the sort is serial or parallel. The best general-purpose sorting algorithms run in O(n log n) time. Some of the simpler ones are O(n^2), which means they get slow fast on big datasets.

Bubble Sort

Bubble sort is the one everyone learns first. The idea is dead simple: walk through the list, compare each pair of neighbors, and swap them if they’re out of order. Keep doing that until nothing gets swapped. The smallest (or largest) values “bubble” to their correct position.

The downside? It’s O(n^2). Not great for anything bigger than a small list.

Here’s the Go implementation from the book:

package main

import "fmt"

func bubbleSorter(integers [11]int) {
    var num int
    num = 11
    var isSwapped bool
    isSwapped = true
    for isSwapped {
        isSwapped = false
        var i int
        for i = 1; i < num; i++ {
            if integers[i-1] > integers[i] {
                var temp = integers[i]
                integers[i] = integers[i-1]
                integers[i-1] = temp
                isSwapped = true
            }
        }
    }
    fmt.Println(integers)
}

func main() {
    var integers [11]int = [11]int{31, 13, 12, 4, 18, 16, 7, 2, 3, 0, 10}
    fmt.Println("Bubble Sorter")
    bubbleSorter(integers)
}

The isSwapped flag is a nice optimization. If you go through the entire array without swapping anything, the array is already sorted and you can stop early. Without that flag, you’d keep looping even when there’s nothing left to do.

Notice the function takes a fixed-size array [11]int, not a slice. That’s a bit unusual for Go, and in practice you’d probably use a slice instead. But for learning purposes it gets the job done.

Selection Sort

Selection sort splits the collection into two parts: sorted and unsorted. It repeatedly finds the smallest element in the unsorted part and moves it to the end of the sorted part. Also O(n^2), and actually performs worse than insertion sort in most cases.

package main

import "fmt"

func SelectionSorter(elements []int) {
    var i int
    for i = 0; i < len(elements)-1; i++ {
        var min int
        min = i
        var j int
        for j = i + 1; j <= len(elements)-1; j++ {
            if elements[j] < elements[min] {
                min = j
            }
        }
        swap(elements, i, min)
    }
}

func swap(elements []int, i int, j int) {
    var temp int
    temp = elements[j]
    elements[j] = elements[i]
    elements[i] = temp
}

func main() {
    var elements []int
    elements = []int{11, 4, 18, 6, 19, 21, 71, 13, 15, 2}
    fmt.Println("Before Sorting ", elements)
    SelectionSorter(elements)
    fmt.Println("After Sorting", elements)
}

The outer loop picks a position, and the inner loop finds the smallest remaining element. Then swap puts it in place. Straightforward, and easy to reason about. The separate swap function is a nice touch for readability.

Insertion Sort

Insertion sort builds the final sorted array one element at a time. Think of it like sorting a hand of cards: you pick up one card at a time and slide it into the right spot among the cards you’ve already sorted. It’s O(n^2) but tends to be faster than bubble sort and selection sort in practice, especially on nearly-sorted data.

The book generates random data to sort using a helper function:

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func randomSequence(num int) []int {
    var sequence []int
    sequence = make([]int, num, num)
    rand.Seed(time.Now().UnixNano())
    var i int
    for i = 0; i < num; i++ {
        sequence[i] = rand.Intn(999) - rand.Intn(999)
    }
    return sequence
}

That rand.Intn(999) - rand.Intn(999) trick gives you numbers in the range of roughly -998 to 998. It’s a quick way to get both positive and negative values without extra logic.

The actual sorting function:

func InsertionSorter(elements []int) {
    var n = len(elements)
    var i int

    for i = 1; i < n; i++ {
        var j int
        j = i
        for j > 0 {
            if elements[j-1] > elements[j] {
                elements[j-1], elements[j] = elements[j], elements[j-1]
            }
            j = j - 1
        }
    }
}

func main() {
    var sequence []int
    sequence = randomSequence(24)
    fmt.Println("\n^^^^^^ Before Sorting ^^^ \n\n", sequence)
    InsertionSorter(sequence)
    fmt.Println("\n--- After Sorting ---\n\n", sequence, "\n")
}

Notice Go’s multiple assignment syntax: elements[j-1], elements[j] = elements[j], elements[j-1]. That’s a swap without needing a temp variable. Go evaluates the right side before assigning, so this works cleanly. The book uses this in insertion sort but not in bubble sort, which is a little inconsistent but both approaches work fine.

Shell Sort

Shell sort is like insertion sort’s bigger, smarter sibling. Instead of comparing neighboring elements, it compares elements that are far apart, then gradually reduces the gap. This lets elements move to their approximate position faster. It was invented by Donald Shell in 1959.

The gap sequence matters a lot for performance. The book uses gaps based on powers of 2 plus 1:

package main

import "fmt"

func ShellSorter(elements []int) {
    var (
        n         = len(elements)
        intervals = []int{1}
        k         = 1
    )

    for {
        var interval int
        interval = power(2, k) + 1
        if interval > n-1 {
            break
        }
        intervals = append([]int{interval}, intervals...)
        k++
    }
    var interval int
    for _, interval = range intervals {
        var i int
        for i = interval; i < n; i += interval {
            var j int
            j = i
            for j > 0 {
                if elements[j-interval] > elements[j] {
                    elements[j-interval], elements[j] = elements[j], elements[j-interval]
                }
                j = j - interval
            }
        }
    }
}

func power(exponent int, index int) int {
    var power int
    power = 1
    for index > 0 {
        if index&1 != 0 {
            power *= exponent
        }
        index >>= 1
        exponent *= exponent
    }
    return power
}

func main() {
    var elements []int
    elements = []int{34, 202, 13, 19, 6, 5, 1, 43, 506, 12, 20, 28, 17, 100, 25, 4, 5, 97, 1000, 27}
    ShellSorter(elements)
    fmt.Println(elements)
}

A few things to note here. The power function computes exponentiation using bit manipulation, which is faster than a simple loop. The index&1 != 0 check tests if the current bit is set, and index >>= 1 shifts right by one. It’s a standard fast exponentiation technique.

The intervals are built from large to small (prepended to the slice with append([]int{interval}, intervals...)), then the sort processes them in order. Start with big gaps to move elements roughly into place, then smaller gaps for fine-tuning.

Shell sort’s complexity depends on the gap sequence. With the right gaps it can get close to O(n log^2 n), which is much better than the O(n^2) algorithms we’ve seen so far.

Merge Sort

Now we’re getting to the O(n log n) algorithms. Merge sort was invented by John Von Neumann, and it’s a classic example of the divide-and-conquer approach. Split the array in half, recursively sort each half, then merge the two sorted halves together.

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func createArray(num int) []int {
    var array []int
    array = make([]int, num, num)
    rand.Seed(time.Now().UnixNano())
    var i int
    for i = 0; i < num; i++ {
        array[i] = rand.Intn(99999) - rand.Intn(99999)
    }
    return array
}

func MergeSorter(array []int) []int {
    if len(array) < 2 {
        return array
    }
    var middle int
    middle = (len(array)) / 2
    return JoinArrays(MergeSorter(array[:middle]), MergeSorter(array[middle:]))
}

func JoinArrays(leftArr []int, rightArr []int) []int {
    var num int
    var i int
    var j int
    num, i, j = len(leftArr)+len(rightArr), 0, 0
    var array []int
    array = make([]int, num, num)

    var k int
    for k = 0; k < num; k++ {
        if i > len(leftArr)-1 && j <= len(rightArr)-1 {
            array[k] = rightArr[j]
            j++
        } else if j > len(rightArr)-1 && i <= len(leftArr)-1 {
            array[k] = leftArr[i]
            i++
        } else if leftArr[i] < rightArr[j] {
            array[k] = leftArr[i]
            i++
        } else {
            array[k] = rightArr[j]
            j++
        }
    }
    return array
}

func main() {
    var elements []int
    elements = createArray(40)
    fmt.Println("\n Before Sorting \n\n", elements)
    fmt.Println("\n-After Sorting\n\n", MergeSorter(elements), "\n")
}

The MergeSorter function is beautifully recursive. If the array has fewer than 2 elements, it’s already sorted, so just return it. Otherwise split it down the middle and recursively sort both halves. The real work happens in JoinArrays.

JoinArrays walks through both sorted sub-arrays with two pointers (i and j), always picking the smaller element to put next in the result. The four if/else conditions handle the cases: left exhausted, right exhausted, left is smaller, right is smaller.

Merge sort is great for linked lists because it doesn’t need random access. The trade-off is that it needs O(n) extra space for the merged array. The book mentions it’s the best algorithm for sorting a linked list, which is true.

Quick Sort

Quick sort is probably the most popular sorting algorithm in practice. When parallelized, it’s 2-3x faster than merge sort and heap sort. It’s O(n log n) on average, though it can degrade to O(n^2) in the worst case (when the pivot choice is bad). The book describes it as a “space-optimized version of the binary tree sort algorithm.”

The idea: pick a pivot element, partition the array so everything smaller is on the left and everything bigger is on the right, then recursively sort both sides.

package main

import "fmt"

func QuickSorter(elements []int, below int, upper int) {
    if below < upper {
        var part int
        part = divideParts(elements, below, upper)
        QuickSorter(elements, below, part-1)
        QuickSorter(elements, part+1, upper)
    }
}

func divideParts(elements []int, below int, upper int) int {
    var center int
    center = elements[upper]
    var i int
    i = below
    var j int
    for j = below; j < upper; j++ {
        if elements[j] <= center {
            swap(&elements[i], &elements[j])
            i += 1
        }
    }
    swap(&elements[i], &elements[upper])
    return i
}

func swap(element1 *int, element2 *int) {
    var val int
    val = *element1
    *element1 = *element2
    *element2 = val
}

func main() {
    var num int

    fmt.Print("Enter Number of Elements: ")
    fmt.Scan(&num)

    var array = make([]int, num)

    var i int
    for i = 0; i < num; i++ {
        fmt.Print("array[", i, "]: ")
        fmt.Scan(&array[i])
    }

    fmt.Print("Elements: ", array, "\n")
    QuickSorter(array, 0, num-1)
    fmt.Print("Sorted Elements: ", array, "\n")
}

A few things worth noticing. The swap function here uses pointers (*int) instead of passing a slice and indices like we saw in selection sort. Both approaches work, but the pointer version is more flexible since it doesn’t need to know about the slice.

The divideParts function picks the last element as the pivot (center). It then walks through the array, moving anything smaller than or equal to the pivot to the left side. The variable i tracks where the next “small” element should go. After the loop, the pivot gets placed at position i, and that position is returned so the recursive calls know where to split.

This main method is different from the others because it reads input from the user with fmt.Scan. The others just hardcode values or generate random ones.

Wrapping Up

That’s six sorting algorithms in Go, from the simple O(n^2) ones (bubble, selection, insertion) to the more practical ones (shell, merge, quick). Here’s a quick comparison:

For real-world Go code, you’d usually just use sort.Slice from the standard library. But understanding how these algorithms work helps you pick the right one when performance matters, or when you’re working in a constrained environment.

In Part 2, we’ll cover the rest of Chapter 8: searching algorithms (linear, binary, interpolation), recursion, and hashing.