Counting Sort

@counting_sort

Counting Sort is a sorting algorithm that does not compare elements. Instead, it counts how many times each number appears and uses that information to place elements directly in their correct position.

Pseudo-code
function counting_sort(arr):

  # Step 1: Find the maximum value
  max_val = find_max(arr)

  # Step 2: Create count array and initialize with 0
  count = array of size (max_val + 1) filled with 0

  # Step 3: Count occurrences
  for each element in arr:
    count[element] = count[element] + 1

  # Step 4: Build cumulative counts
  for i from 1 to max_val:
    count[i] = count[i] + count[i - 1]

  # Step 5: Build output array
  output = array of size length(arr)

  # Step 6: Place elements in correct positions
  for each element in arr (from right to left):
    output[count[element] - 1] = element
    count[element] = count[element] - 1

  return output
  • arr Input list of numbers you want to sort.
  • max_val Largest number in the list. This tells us how big our counting array should be.
  • count A helper array where each index represents a number, and the value at that index tells how many times it appears.
  • output Final sorted array where elements are placed in correct order.
  • 0 The starting index and also represents the smallest possible counted value.
Recipe Steps
1

Count how many of each number you have — Imagine you have numbers like labels on boxes. First, count how many of each label exist.

2

Make a list where each position represents a number, and store how many times it appears.

3

Turn counts into positions — Convert counts so they tell you where each number should go in the final sorted list.

4

Go through your original list and place each number into its correct position in the output array.

5

After placing everything, you get a fully sorted list.

Questions & Answers

It does not compare elements; it counts occurrences instead.

They tell us the exact position where each element should go.

When the range of numbers is small compared to the number of elements.

It means number 3 should be placed at index 4 (position 5 in 1-based counting).
- Time complexity is O(n + k), where k is the range of values.
- Very fast when numbers are small and limited.
- Tip: Iterate from right to left when building output to keep it stable.
- Common mistake: Using it when values are very large (wastes memory).
- Works best for integers, not general data like strings unless mapped.

Related Algorithms
Backtracking

Backtracking is a problem-solving technique used in algorithms to find a solution by exploring all possible solutions and retracting when a dead end is reached. It's often used for solving puzzles, finding paths, or scheduling tasks.

View
Binary Search

Binary Search is a very fast algorithm used to find a value in a sorted list by repeatedly cutting the search space in half until the item is found or nothing is left.

View
Boyer–Moore string-search algorithm

The Boyer–Moore string-search algorithm is a fast string searching algorithm that is often used in text editors and compilers. It does this by trying to match the pattern from the end of the string, making it efficient for large strings. It's used when you need to find a substring within a large text or string.

View