What it is counting sort

Counting Sort is an algorithm for sorting keys that are small integers and repeatable values. However, it is not recommended for large keys because the logic consists of using an array where the value serves as the index of the array to store the counts of each key. Thus, the length of this array is calculated as store = len(max - min + 1). After that, the algorithm rebuilds the order of the values according to their counts and positions.

Performance

• Worst-case time complexity: O(n + k), where n is the number of elements to be sorted, and k is the range of the key values.
• Worst-case space complexity: O(n + k)

When to Use counting sort

Counting Sort is most effective when:

• The range of input values (k) is not significantly larger than the number of elements (n).
• The values are integers or can be mapped to integers, and they are within a known range.
• Additionally, the data contains many repeated values, making the counting approach efficient.

Limitations

• On the other hand, it is not suitable for sorting floating-point numbers, strings, or large ranges of integers without modification.
• Moreover, it consumes extra space proportional to the range of input values, which can be inefficient if the range is large.

Implementation counting sort using Golang

package main

import "fmt"

func countingSort(nums []int) []int {
	max := nums[0]
	min := nums[0]

	for _, num := range nums {
		if num > max {
			max = num
		}
		if num < min {
			min = num
		}
	}

	counter := make([]int, max-min+1)
	for _, num := range nums {
		counter[num-min]++
	}

	index := 0
	for i, c := range counter {
		for c > 0 {
			nums[index] = i + min
			index++
			c--
		}
	}

	return nums
}

func main() {

	nums := []int{4, 2, -3, 6, -1, 0, 2, -3}
	nums2 := []int{4, 2, 1, 1, 1, 0, 2, 13}

	fmt.Println(countingSort(nums))
	fmt.Println(countingSort(nums2))
}