Sorting is one of the most essential parts of computer science. Whether you are arranging names alphabetically, organizing scores in a game, or managing large sets of data, sorting algorithms help make data easier to handle and understand. Among many sorting methods available, Counting Sort stands out for its simplicity and impressive speed — especially when working with integers in a limited range.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is not a comparison-based algorithm like Quick Sort or Merge Sort. Instead, it works by counting the number of occurrences of each unique element in the input array. These counts are then used to determine the correct position of each element in the sorted array. Because it doesn’t compare elements directly, Counting Sort can achieve a linear time complexity — making it faster than most sorting methods when used correctly.
This algorithm is perfect when you know the range of the numbers you are dealing with. It’s often used in cases such as sorting grades, ranking systems, or any situation where the values fall within a small, known range. In this article, we’ll go through several GoLang programs that implement Counting Sort in different ways. By the end, you’ll have a clear understanding of how it works and how you can use it in your own Go projects.
Program 1: Basic Counting Sort Implementation
This first program is a simple version of Counting Sort in Go. It uses an integer array and sorts it in ascending order by counting the frequency of each element.
package main
import "fmt"
func countingSort(arr []int) []int {
if len(arr) == 0 {
return arr
}
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
count := make([]int, max+1)
for _, num := range arr {
count[num]++
}
index := 0
for i := 0; i <= max; i++ {
for count[i] > 0 {
arr[index] = i
index++
count[i]--
}
}
return arr
}
func main() {
arr := []int{4, 2, 2, 8, 3, 3, 1}
fmt.Println("Original array:", arr)
sorted := countingSort(arr)
fmt.Println("Sorted array:", sorted)
}In this program, the algorithm first finds the maximum element in the array. Then it creates a “count” array to keep track of how many times each number appears. After counting, it places each number in its correct position. This approach is simple and fast when the range of numbers is not too large. Beginners can easily follow this logic and see how Counting Sort avoids comparisons completely.
Program 2: Counting Sort Supporting Negative Numbers
The first version only worked for non-negative integers. Let’s improve it so that it can handle both positive and negative numbers.
package main
import "fmt"
func countingSortWithNegatives(arr []int) []int {
if len(arr) == 0 {
return arr
}
min, max := arr[0], arr[0]
for _, num := range arr {
if num < min {
min = num
}
if num > max {
max = num
}
}
rangeVal := max - min + 1
count := make([]int, rangeVal)
for _, num := range arr {
count[num-min]++
}
index := 0
for i := 0; i < rangeVal; i++ {
for count[i] > 0 {
arr[index] = i + min
index++
count[i]--
}
}
return arr
}
func main() {
arr := []int{-5, -10, 0, -3, 8, 5, -1, 10}
fmt.Println("Original array:", arr)
sorted := countingSortWithNegatives(arr)
fmt.Println("Sorted array (with negatives):", sorted)
}This version calculates both the minimum and maximum values to handle negative numbers properly. It then adjusts the count array using an offset (num - min) so that even negative numbers fit in the count array. This makes the algorithm much more flexible and usable in a wider range of applications.
Program 3: Stable Counting Sort
The next version is a stable implementation of Counting Sort. A stable sort keeps elements with equal values in the same order as they appeared in the original array. This property is important when sorting complex data structures like records or pairs.
package main
import "fmt"
func stableCountingSort(arr []int) []int {
if len(arr) == 0 {
return arr
}
max := arr[0]
for _, num := range arr {
if num > max {
max = num
}
}
count := make([]int, max+1)
for _, num := range arr {
count[num]++
}
for i := 1; i <= max; i++ {
count[i] += count[i-1]
}
output := make([]int, len(arr))
for i := len(arr) - 1; i >= 0; i-- {
output[count[arr[i]]-1] = arr[i]
count[arr[i]]--
}
return output
}
func main() {
arr := []int{4, 2, 2, 8, 3, 3, 1}
fmt.Println("Original array:", arr)
sorted := stableCountingSort(arr)
fmt.Println("Stable sorted array:", sorted)
}This program enhances the earlier logic by modifying how the count array is processed. Instead of directly placing elements, it converts the counts into prefix sums, which help determine the final positions of each element. By processing the array from right to left, it ensures stability — that is, equal elements retain their original order.
Program 4: Counting Sort for Characters
Counting Sort can also be applied to non-numeric data, like characters or letters. This program demonstrates how to sort characters using their ASCII values.
package main
import "fmt"
func countingSortChars(arr []rune) []rune {
max := arr[0]
for _, ch := range arr {
if ch > max {
max = ch
}
}
count := make([]int, max+1)
for _, ch := range arr {
count[ch]++
}
index := 0
for i := 0; i <= int(max); i++ {
for count[i] > 0 {
arr[index] = rune(i)
index++
count[i]--
}
}
return arr
}
func main() {
arr := []rune{'d', 'a', 'c', 'b', 'e'}
fmt.Println("Original characters:", string(arr))
sorted := countingSortChars(arr)
fmt.Println("Sorted characters:", string(sorted))
}In this version, each character is treated as its integer ASCII value. The algorithm counts the occurrences of each character and reconstructs the array in order. This example shows how flexible Counting Sort can be — from numbers to letters, the same idea applies beautifully.
Frequently Asked Questions (FAQ)
Below are some common questions beginners often have about Counting Sort in GoLang.
Q1: What is Counting Sort best used for?
Counting Sort works best when sorting integers or objects that can be easily mapped to small integer ranges. It is especially useful when the range of numbers is not significantly larger than the number of items to sort.
Q2: Is Counting Sort a stable sorting algorithm?
By default, Counting Sort is not stable, but it can be made stable with slight modifications — as shown in Program 3.
Q3: Can Counting Sort handle negative numbers?
Yes, it can. You just need to adjust the counting array by accounting for the minimum value in the array, as shown in Program 2.
Q4: What is the time complexity of Counting Sort?
Counting Sort runs in O(n + k) time, where n is the number of elements and k is the range of input values.
Q5: What are the limitations of Counting Sort?
Counting Sort can use a lot of memory if the range of numbers (k) is very large. It’s ideal for datasets where the range is relatively small and well-known.
Conclusion
Counting Sort is one of the simplest and fastest sorting algorithms when used in the right situations. It doesn’t rely on element comparisons but instead counts occurrences, which gives it excellent performance for small or medium-sized ranges of integers.
In GoLang, implementing Counting Sort is straightforward, and through the examples above, you’ve seen how it can be adapted to handle negative numbers, characters, and even stability requirements. It’s an excellent algorithm for beginners to learn because it strengthens understanding of arrays, indexing, and data handling in Go.
Take time to experiment with different inputs and ranges. Try visualizing how the count array changes as elements are counted and placed. Once you understand that process, you’ll find that Counting Sort isn’t just efficient — it’s elegant in its simplicity.
