Introduction

When you need to sort one million integers but every value is known to be between 1 and 100, comparison-based sorting is no longer the best tool. The fastest practical solution is usually counting sort, because the value range is tiny compared with the number of items.

Why Counting Sort Fits This Problem

General-purpose sorts such as quicksort, mergesort, or heapsort spend time comparing elements. That is necessary when values can be arbitrary, but here the domain is fixed and very small. Instead of asking "which element is smaller," you can simply count how many times each value appears.

For numbers from 1 through 100, the count array needs only 101 slots if you ignore index 0.

The algorithm is:

1. create an array of counters
2. scan the million integers once and increment the appropriate counter
3. rebuild the sorted result by writing each number according to its count

That runs in O(n + k) time, where n is the number of values and k is the range size. Here k is only 100, so the work is effectively linear in the size of the input.

A Simple Python Implementation

1def counting_sort(values):
2    counts = [0] * 101
3
4    for value in values:
5        counts[value] += 1
6
7    result = []
8    for value in range(1, 101):
9        result.extend([value] * counts[value])
10
11    return result
12
13
14data = [7, 3, 7, 1, 100, 3, 2]
15print(counting_sort(data))

Output:

[1, 2, 3, 3, 7, 7, 100]

This is already very fast. For one million integers in a range of size 100, the counting pass dominates and is extremely cache-friendly.

In-Place Overwrite Is Even Better

If you do not need to preserve the original array separately, you can overwrite it in place after counting.

1def counting_sort_in_place(values):
2    counts = [0] * 101
3
4    for value in values:
5        counts[value] += 1
6
7    index = 0
8    for value in range(1, 101):
9        for _ in range(counts[value]):
10            values[index] = value
11            index += 1
12
13
14data = [7, 3, 7, 1, 100, 3, 2]
15counting_sort_in_place(data)
16print(data)

This avoids allocating a second large result list.

Why General Sorting Loses Here

A comparison sort has to do more work than necessary because it keeps asking relative-order questions for values that come from a tiny known set. Even an O(n log n) sort with a very good implementation still wastes effort compared with a direct frequency count in this scenario.

That does not mean comparison sorts are bad. It means the data distribution gives you a stronger option.

Histograms and Sorting Are Almost the Same Here

For a range this small, the "sorted form" is essentially just a histogram expanded back into a list. If your downstream task can work directly from counts, you may not even need to rebuild the full sorted array.

For example, if the next step only needs:

• frequency of each value
• median
• percentile cutoffs

then the count array itself may be enough, which is even cheaper than materializing the sorted output.

Common Pitfalls

The biggest pitfall is reaching automatically for a library sort without using the range information. With unrestricted inputs that is reasonable, but with values limited to 1 through 100, you are leaving performance on the table.

Another common mistake is forgetting to validate the input range. Counting sort assumes values stay within the expected bounds; one out-of-range value can produce an index error or corrupt the counts.

Developers also sometimes rebuild the full output when all they really needed was the frequency table. If a histogram answers the business question, stop there.

Summary

• For one million integers restricted to 1 through 100, counting sort is usually the fastest approach.
• The algorithm runs in O(n + k) time, and here k is only 100.
• A count array plus reconstruction is simpler and faster than general comparison sorting.
• If you only need frequencies or order statistics, the count array may be enough by itself.
• Validate the input range before relying on counting sort logic.