Why Counting Sort Algorithm in DSA Go?

The Big Idea

What if you could sort thousands of items instantly without comparing each one?

The Scenario

Imagine you have a big box of colored balls, and you want to arrange them by color quickly. If you try to pick each ball and compare it with every other ball to find its place, it will take a long time and be very tiring.

The Problem

Sorting by comparing each ball to others is slow and confusing. You might lose track or make mistakes, especially if there are many balls or colors. This manual way wastes time and energy.

The Solution

Counting Sort counts how many balls of each color there are first. Then, it uses these counts to place each ball directly in the right order without comparing them one by one. This makes sorting fast and simple.

Before vs After

✗ Before

for i := 0; i < len(arr); i++ {
  for j := i + 1; j < len(arr); j++ {
    if arr[j] < arr[i] {
      arr[i], arr[j] = arr[j], arr[i]
    }
  }
}

✓ After

count := make([]int, max+1)
for _, num := range arr {
  count[num]++
}
index := 0
for num, c := range count {
  for c > 0 {
    arr[index] = num
    index++
    c--
  }
}

What It Enables

Counting Sort lets you sort items quickly when you know the range of values, making big sorting tasks easy and fast.

Real Life Example

Sorting exam scores from 0 to 100 for a large class quickly to find the top performers without comparing every score to each other.

Key Takeaways

Manual comparison sorting is slow for many items.

Counting Sort counts occurrences to sort efficiently.

Best for sorting numbers within a known small range.