Sorting is one of the most important operations in computer science, and there are many ways to do it. From simple algorithms like Bubble Sort and Insertion Sort to more advanced ones like Merge Sort and Quick Sort, sorting algorithms help arrange data so it becomes easier to work with. But when it comes to sorting numbers quickly and efficiently — especially integers — Radix Sort is one of the fastest and most fascinating algorithms you can learn.
with hands-on learning.
get the skills and confidence to land your next move.
Unlike comparison-based algorithms, Radix Sort doesn’t compare elements directly. Instead, it looks at each digit (or bit) of a number and sorts based on those digits — starting from the least significant digit (the units place) and moving up to the most significant one (the highest place value). Because of this unique approach, Radix Sort can handle large datasets of numbers very efficiently. It’s widely used in scenarios like sorting IDs, phone numbers, or large lists of integers where speed and precision are essential.
Program 1: Basic Radix Sort in GoLang
This first program introduces the basic version of Radix Sort in GoLang. It works by sorting numbers digit by digit using a helper function that performs Counting Sort on each digit.
package main
import "fmt"
func getMax(arr []int) int {
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
return max
}
func countingSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
index := (arr[i] / exp) % 10
count[index]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
index := (arr[i] / exp) % 10
output[count[index]-1] = arr[i]
count[index]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func radixSort(arr []int) {
max := getMax(arr)
for exp := 1; max/exp > 0; exp *= 10 {
countingSort(arr, exp)
}
}
func main() {
numbers := []int{170, 45, 75, 90, 802, 24, 2, 66}
fmt.Println("Original array:", numbers)
radixSort(numbers)
fmt.Println("Sorted array:", numbers)
}This program begins by finding the largest number in the array to determine the number of digits to sort. It then performs Counting Sort on each digit, starting from the least significant (units) place to the most significant. By the end of the process, the array is fully sorted. Beginners can clearly see how breaking down the sorting process into smaller digit-level steps makes it easy to follow and efficient to run.
Program 2: Radix Sort with Step-by-Step Printing
This next program is perfect for beginners who like to see what’s happening under the hood. It includes print statements after each sorting pass, so you can visually track how the array changes as each digit is sorted.
package main
import "fmt"
func getMax(arr []int) int {
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
return max
}
func countingSortWithPrint(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
index := (arr[i] / exp) % 10
count[index]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
index := (arr[i] / exp) % 10
output[count[index]-1] = arr[i]
count[index]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
fmt.Println("After sorting by digit", exp, ":", arr)
}
func radixSortWithPrint(arr []int) {
max := getMax(arr)
for exp := 1; max/exp > 0; exp *= 10 {
countingSortWithPrint(arr, exp)
}
}
func main() {
numbers := []int{432, 8, 530, 90, 88, 231, 11, 45}
fmt.Println("Original array:", numbers)
radixSortWithPrint(numbers)
fmt.Println("Final sorted array:", numbers)
}Here, each time the algorithm sorts by a digit, it prints the intermediate array. This step-by-step output is especially useful for beginners trying to understand how Radix Sort gradually organizes numbers. It’s like watching the algorithm come alive and do its job in slow motion.
Program 3: Radix Sort for Descending Order
Radix Sort usually sorts in ascending order, but with a few changes, you can easily reverse the order. This version sorts the array in descending order.
package main
import "fmt"
func getMax(arr []int) int {
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
return max
}
func countingSortDesc(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
index := (arr[i] / exp) % 10
count[index]++
}
for i := 8; i >= 0; i-- {
count[i] += count[i+1]
}
for i := n - 1; i >= 0; i-- {
index := (arr[i] / exp) % 10
output[count[index]-1] = arr[i]
count[index]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func radixSortDesc(arr []int) {
max := getMax(arr)
for exp := 1; max/exp > 0; exp *= 10 {
countingSortDesc(arr, exp)
}
}
func main() {
numbers := []int{23, 345, 5467, 12, 2345, 9852}
fmt.Println("Original array:", numbers)
radixSortDesc(numbers)
fmt.Println("Sorted array in descending order:", numbers)
}By reversing the counting process, this version places larger digits first, sorting numbers from largest to smallest. It’s a neat example of how simple logic changes can make algorithms flexible for different use cases.
Program 4: Radix Sort Using Recursion
While most implementations use loops, Radix Sort can also be written recursively. This version demonstrates how recursion can simplify certain algorithmic steps and make the code more readable for learners who already understand recursive thinking.
package main
import "fmt"
func getMax(arr []int) int {
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
return max
}
func countingSortRecursive(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
index := (arr[i] / exp) % 10
count[index]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
index := (arr[i] / exp) % 10
output[count[index]-1] = arr[i]
count[index]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func radixSortRecursive(arr []int, exp, max int) {
if max/exp == 0 {
return
}
countingSortRecursive(arr, exp)
radixSortRecursive(arr, exp*10, max)
}
func main() {
numbers := []int{120, 45, 75, 2, 24, 66, 802, 90}
fmt.Println("Original array:", numbers)
max := getMax(numbers)
radixSortRecursive(numbers, 1, max)
fmt.Println("Sorted array (recursive):", numbers)
}This version achieves the same result as the iterative approach but uses recursion to handle each digit level. It’s a good way to practice thinking recursively and see how loops can be replaced with recursive calls in GoLang.
Program 5: Radix Sort for Integers with Negatives
This version of Radix Sort sorts an array of integers, including negatives. The algorithm shifts digit indices in counting sort to handle negative numbers properly, ensuring correct ascending order.
package main
import (
"fmt"
"math"
)
// Get maximum absolute value from integer array
func getMaxAbs(arr []int) int {
max := 0
for _, n := range arr {
if int(math.Abs(float64(n))) > max {
max = int(math.Abs(float64(n)))
}
}
return max
}
// Counting sort for integers by specific digit
func countingSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 19) // digits -9..9
for i := 0; i < n; i++ {
index := (arr[i]/exp)%10 + 9
count[index]++
}
for i := 1; i < 19; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
index := (arr[i]/exp)%10 + 9
output[count[index]-1] = arr[i]
count[index]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
// Recursive radix sort for integers
func radixSort(arr []int, exp, max int) {
if max/exp == 0 {
return
}
countingSort(arr, exp)
radixSort(arr, exp*10, max)
}
func main() {
numbers := []int{120, -45, 75, -2, 24, 66, 802, -90}
fmt.Println("Original array:", numbers)
max := getMaxAbs(numbers)
radixSort(numbers, 1, max)
fmt.Println("Sorted array (integers with negatives):", numbers)
}This program sorts integers directly. Negative numbers are handled by shifting digit indices in counting sort, ensuring correct ascending order.
Program 6: Radix Sort for Fixed-Length Strings with Negatives
This program sorts numeric strings using radix sort. Strings are temporarily padded with leading zeros to ensure uniform length. Negative numbers are handled separately, preserving the original strings while allowing correct ascending order.
package main
import (
"fmt"
"strconv"
)
// padStringNumbers converts numeric strings to fixed-length strings with leading zeros
func padStringNumbers(arr []string, length int) []string {
padded := make([]string, len(arr))
for i, s := range arr {
num, _ := strconv.Atoi(s)
sign := ""
if num < 0 {
sign = "-"
num = -num
}
padded[i] = fmt.Sprintf("%s%0*d", sign, length, num)
}
return padded
}
// countingSortByDigit sorts strings by a specific digit index
func countingSortByDigit(arr []string, index int) []string {
count := make([][]string, 10)
for _, s := range arr {
digit := s[index] - '0'
count[digit] = append(count[digit], s)
}
sorted := []string{}
for i := 0; i < 10; i++ {
sorted = append(sorted, count[i]...)
}
return sorted
}
// radixSortStrings sorts fixed-length numeric strings
func radixSortStrings(arr []string) []string {
if len(arr) == 0 {
return arr
}
length := len(arr[0])
for i := length - 1; i >= 0; i-- {
arr = countingSortByDigit(arr, i)
}
return arr
}
func main() {
numbers := []string{"5", "23", "120", "7", "-802"}
// Determine maximum length for padding
maxLen := 0
for _, s := range numbers {
n := len(s)
if s[0] == '-' {
n--
}
if n > maxLen {
maxLen = n
}
}
// Pad numbers for sorting
padded := padStringNumbers(numbers, maxLen)
// Separate negatives and positives
negatives := []string{}
positives := []string{}
negMap := map[string]string{}
posMap := map[string]string{}
for i, s := range padded {
if s[0] == '-' {
val := s[1:]
negatives = append(negatives, val)
negMap[val] = numbers[i]
} else {
positives = append(positives, s)
posMap[s] = numbers[i]
}
}
// Sort each group
negatives = radixSortStrings(negatives)
positives = radixSortStrings(positives)
// Reverse negatives and restore original strings
for i, j := 0, len(negatives)-1; i < j; i, j = i+1, j-1 {
negatives[i], negatives[j] = negatives[j], negatives[i]
}
sortedNegatives := []string{}
for _, s := range negatives {
sortedNegatives = append(sortedNegatives, negMap[s])
}
sortedPositives := []string{}
for _, s := range positives {
sortedPositives = append(sortedPositives, posMap[s])
}
// Combine results
sorted := append(sortedNegatives, sortedPositives...)
fmt.Println("Sorted array (strings):", sorted)
}This approach allows radix sort to correctly order numeric strings even when negatives are present. Padding ensures digits align properly, while separating negatives guarantees they appear in the correct order relative to positives. The original string values remain unchanged, making the output suitable for display or further processing.
Program 7: Radix Sort for Fixed-Length Strings (Non-Negative Only)
This version sorts numeric strings when all numbers are non-negative. Since there are no negative values, the algorithm is simpler and does not require separate handling.
package main
import (
"fmt"
"strconv"
)
// padStringNumbers converts numeric strings to fixed-length strings with leading zeros
func padStringNumbers(arr []string, length int) []string {
padded := make([]string, len(arr))
for i, s := range arr {
num, _ := strconv.Atoi(s)
padded[i] = fmt.Sprintf("%0*d", length, num)
}
return padded
}
// countingSortByDigit sorts strings by a specific digit index
func countingSortByDigit(arr []string, index int) []string {
count := make([][]string, 10)
for _, s := range arr {
digit := s[index] - '0'
count[digit] = append(count[digit], s)
}
sorted := []string{}
for i := 0; i < 10; i++ {
sorted = append(sorted, count[i]...)
}
return sorted
}
// radixSortStrings sorts fixed-length numeric strings
func radixSortStrings(arr []string) []string {
if len(arr) == 0 {
return arr
}
length := len(arr[0])
for i := length - 1; i >= 0; i-- {
arr = countingSortByDigit(arr, i)
}
return arr
}
func main() {
numbers := []string{"5", "23", "120", "7"}
// Determine maximum length for padding
maxLen := 0
for _, s := range numbers {
if len(s) > maxLen {
maxLen = len(s)
}
}
// Pad numbers for sorting
padded := padStringNumbers(numbers, maxLen)
// Sort numbers
sortedPadded := radixSortStrings(padded)
// Map back to original strings
paddedMap := map[string]string{}
for i, s := range padded {
paddedMap[s] = numbers[i]
}
sorted := []string{}
for _, s := range sortedPadded {
sorted = append(sorted, paddedMap[s])
}
fmt.Println("Sorted array (non-negative strings):", sorted)
}For non-negative strings, radix sort can operate directly after padding. The internal padding aligns digits for sorting, while mapping back to the original strings ensures the output preserves the exact input format. This makes it ideal for situations where numbers are stored as strings but need numeric ordering without altering the original representation.
Frequently Asked Questions (FAQ)
Radix Sort often sparks curiosity because it works differently from most sorting algorithms. Here are some common questions that beginners ask.
Q1: What makes Radix Sort different from other sorting algorithms?
Radix Sort doesn’t compare numbers directly. Instead, it sorts based on each digit, making it very efficient for sorting integers or fixed-length strings.
Q2: What is the time complexity of Radix Sort?
The time complexity is O(nk), where n is the number of elements and k is the number of digits. For small digit counts, it’s almost linear — much faster than comparison sorts like Merge or Quick Sort.
Q3: Can Radix Sort handle negative numbers?
Traditional Radix Sort works with non-negative integers. However, with some modifications, it can be adapted to handle negative values as well.
Q4: Why does Radix Sort use Counting Sort internally?
Counting Sort is a stable sorting algorithm that sorts data based on frequency. It’s ideal for sorting digits within Radix Sort since it maintains order efficiently.
Q5: Where is Radix Sort used in real-world applications?
It’s used in systems that deal with large amounts of numerical data, such as databases, digital signal processing, and even computer graphics rendering.
Conclusion
Radix Sort is a brilliant algorithm that teaches us how sorting can be done without directly comparing elements. Its unique digit-by-digit approach makes it both efficient and fascinating to study. Learning how to implement it in GoLang not only deepens your understanding of algorithms but also strengthens your skills in problem-solving and logical thinking.
By experimenting with recursive, step-by-step, and descending versions, you can see just how flexible and powerful this sorting algorithm can be. Keep exploring and tweaking your code — every new variation brings you closer to mastering sorting algorithms and writing efficient GoLang programs.
