Radix Sort in Go (Golang)

Radix Sort is a relatively old (discovered in 1887 by Herman Hollerith), non-comparitive integer sorting algorithm, which sorts data by comparing various integers individual digit position and value. In many ways Radix Sort in Go reflects and builds off Counting Sort, and I recommend reviewing that algorithm as well.

Radix Sort

Essentially, the algorithm is is follows:

• Receive an unsorted array of integers, often referred/represent a key
• Iterate from most to least or least to most significant digits
• Each iteration sort all of the values of the current significant digit the array

* A key in this case, is an integer value, which is associated with other data, such as birth date, location, etc.

To better demonstrate, we will complete an example problem with four integers to sort:

Original: 100, 12, 1, 5

{ 100, 12, 1, 5 } -> { 100, 1, 12, 5 }
{ 100, 1, 12, 5 } -> { 1, 5, 100, 12 }
{ 1, 5, 100, 12 } -> { 1, 5, 12, 100 }

Sorted: 1, 5, 12, 100

That’s it! If you carefully watch the “100” value through various iterations, you’ll notice each time we simply move one significant digit to the left and resort using that digit. It is also possible to go left to right, i.e. most significant digit to least significant digit, but I chose this implementation.

Example by Hand

Implementing this algorithm requires a bit more finesse than I let on. First, let me state that there are several ways to implement Radix Sort, and this is not the sole correct method. In order to efficiently implement Radix Sort, we use something called “buckets” which will store the index of the sorted significant digits, similar to Counting Sort. 

For example, the bucket for iteration one would be as follows:

 array[100, 1, 12, 5] -> bucket[0, 1, 2, 2, 2, 4, 4, 4, 4, 4]

The reason for the repeated numbers is because we have a value of 0, 1, 2, and 5 for the value at the given significant digit (in this case the 1’s place). The implementation I am using adds a number to the bucket[index] when ever there is a new value for a given significant digit. For instance, the reason we repeat 2 twice after the initial 2 is because there is no “3 or 4” in the any of the integers current significant digits, in the array we are sorting (wow that was a mouthful). 

If we then added the number 101 to the list, we would have the following bucket:

 array[100, 101, 1, 12, 5] -> bucket[0, 1, 3, 3, 3, 4, 4, 4, 4, 4]

Notice, the orange 2 has changed to a orange 3, this is because the new 2-value bucket starts at 3rd position in the semi-sorted array. 

Now let’s add the number 8 to the list, we will have the following bucket:

array[100, 101, 1, 12, 5, 8] -> bucket[0, 1, 3, 3, 3, 4, 4, 4, 5, 5]

Reflect that 8 is the 5th index in the sorted significant digit array, represented with the number 5 in the 8th index/position in the bucket array.

• Time: O(nk), where n is the number of elements and k is the number of bits per element
• Space: O(n + k), where n is the number of elements and k is the number of bits per element

Code | Radix Sort in Golang

(viewable/forkable on Github)

package main

import (
	"fmt"
	"strconv"
)

// Finds the largest number in an array
func findLargestNum(array []int) int {
	largestNum := 0

	for i := 0; i < len(array); i++ {
		if array[i] > largestNum {
			largestNum = array[i]
		}
	}
	return largestNum
}

// Radix Sort
func radixSort(array []int) []int {

  fmt.Println("Running Radix Sort on Unsorted List\n")

  // Base 10 is used
	largestNum := findLargestNum(array)
	size := len(array)
	significantDigit := 1
	semiSorted := make([]int, size, size)

	// Loop until we reach the largest significant digit
	for largestNum / significantDigit > 0 {
  
    fmt.Println("\tSorting: " + strconv.Itoa(significantDigit) + "'s place", array)

		bucket := [10]int{0}

		// Counts the number of "keys" or digits that will go into each bucket
		for i := 0; i < size; i++ {
			bucket[(array[i] / significantDigit) % 10]++
		}

		// Add the count of the previous buckets
    // Acquires the indexes after the end of each bucket location in the array
		// Works similar to the count sort algorithm
		for i := 1; i < 10; i++ {
			bucket[i] += bucket[i - 1] 
		}

		// Use the bucket to fill a "semiSorted" array
		for i := size - 1; i >= 0; i-- {
			bucket[(array[i] / significantDigit) % 10]--
			semiSorted[bucket[(array[i] / significantDigit) % 10]] = array[i]
		}

    // Replace the current array with the semisorted array
		for i := 0; i < size; i++ {
			array[i] = semiSorted[i]
		}
    
    fmt.Println("\n\tBucket: ", bucket)
  
    // Move to next significant digit
		significantDigit *= 10 
	}

	return array
}

func main() {

  fmt.Println("\n\nRunning Radix Sort Example in Go!")
  fmt.Println("----------------------------------\n")

	unsortedList :=[]int{10, 2, 303, 4021, 293, 1, 0, 429, 480, 92, 2999, 14}
	fmt.Println("Unsorted List:", unsortedList, "\n")

	sortedList := radixSort(unsortedList)

	fmt.Println("\nSorted List:", sortedList, "\n")
}

Shameless  Plug: It took about 20 minutes to code this up. If you need help with Go programming feel free to book me for tutoring/program writing.

Output:

Running Radix Sort Go Example!
———————————-

Unsorted List: [10 2 303 4021 293 1 0 429 480 92 2999 14]

Running Radix Sort in Golang on Unsorted List

Sorting: 1’s place [10 2 303 4021 293 1 0 429 480 92 2999 14]

Bucket: [0 3 5 7 9 10 10 10 10 10]
Sorting: 10’s place [10 0 480 4021 1 2 92 303 293 14 429 2999]

Bucket: [0 4 6 8 8 8 8 8 8 9]
Sorting: 100’s place [0 1 2 303 10 14 4021 429 480 92 293 2999]

Bucket: [0 7 7 8 9 11 11 11 11 11]
Sorting: 1000’s place [0 1 2 10 14 4021 92 293 303 429 480 2999]

Bucket: [0 10 10 11 11 12 12 12 12 12]

Sorted List: [0 1 2 10 14 92 293 303 429 480 2999 4021]

Feel free to review my article on Radix Sort in C as well, the results are exactly the same as Radix Sort in Go.

Summary

Unfortunately, due to its simplicity and the requirement of fixed-length integer keys, this algorithm is often overlooked or unused. There are several applications of Radix Sort which can be useful, such as parallel computing, but Radix Sort is not really a “general purpose” sorting algorithm. For the average or more general use case quicksort or merge sort is probably a safer bet. If you are still interested I recommend reading further discussion on stack exchange and stack overflow.

Related Articles

• Everyday Algorithms: Pancake Sort
• Using SVD to Obtain Regression Lines
• Introduction to Markov Processes (a.k.a. Markov Chains)
• Everyday Algorithms: Elevator Allocation Algorithm
• I/O Multiplexing using epoll and kqueue System Calls