Counting Sort Implementation in Java

Image Source

Counting sort runs on a different idea than comparison based sorting and treats data as values placed within a known span of integers. It tallies how many times each value appears, and that count guides where everything lands in the final array. The method moves fast when the numeric span stays small and shows how frequency based work replaces element to element checks. It also fits in the wider sorting family by keeping linear time in the right cases while holding stable placement for equal values.

Window Into Counting Mechanics

Sorting with counts moves through a set of steps that feed into one another, and the whole idea feels smoother once those steps fall into place. Comparisons never enter the picture. The method relies on tallies and simple passes that push values toward their final spots. A wide or narrow range both follow the same flow, and the values naturally guide their own positions after the tallies form.

Frequency Tallies As The Core

Counting begins with a pass through the input that builds tallies for every value inside the known span. Each tally lands at an index tied to the value itself. That gives the method a compact picture of how the data spreads out, and it spares any back and forth checks between two values. After those tallies settle, the method already knows how many spaces to reserve for every number that appears.

This scan can show this visually:

The tallies in that array reflect how the values spread through the input. Some cases call for finding the maximum first so the count array matches the range.

The flow stays the same for smaller or larger arrays. Nothing in this step leans on outdated Java features, and the logic stays practical across current runtimes. Some situations work better if the minimum is tracked as well, which keeps the count array tight when values don’t start at zero.

This version sticks to the same idea but keeps the tally range compact. Tallies form the base for the rest of counting mechanics, and the later stages only need these numbers to build exact positions.

Prefix Totals For Placement

Tally counts only tell how many times a value appears. A prefix sweep gives those counts meaning by turning them into boundaries inside the final array. This sweep moves through the count array from left to right, and each slot becomes the total for everything up to that point.

Those accumulated counts form a map of where values should land in sorted order. Each index becomes the upper line for placements, and every value in the input will draw from that number during the final pass.

A shifted range uses the same update:

These totals guide the rest of the method without introducing comparisons. The prefix stage gives the method a way to drop values into place with confidence that every position lines up correctly.

Stable Placement Through Backward Movement

The last stage walks backward through the input and drops values into the output array using the prefix totals. Working from the end keeps equal values in their original order, because later arrivals settle later in the final result. Stability matters in many real workflows, and counting sort reaches that result with a single backward sweep.

The placement step looks like this:

This pass trims the prefix boundary for the value after every placement. Equal values fall into the correct sequence without side steps or extra storage.

Narrowed spans of values follow the same idea with a small adjustment:

The two versions both protect stability. The backward walk gives equal values room to land in the right order with minimal effort. Counting sort closes with a full picture of the sorted array, and every step from tallies through placement remains grounded in modern Java practice.

How Counting Sort Fits Among Other Methods

Sorting has a long family tree, and counting sort holds a spot that feels different from the comparison based group. Many people are used to methods that weigh two values side by side to judge order. Counting sort skips that idea and instead works with tallies and known spans, which places it in a separate corner of the sorting world.

Comparison Free Sorting

Counting sort builds its ordering without putting two values head to head. That alone draws a noticeable line between it and methods like mergesort or heapsort. Those methods depend on checks that decide which value deserves to move forward at every turn. Counting sort instead treats the input as a pool of numbers that fall into a known span and then tallies how often each one appears. That gives the method the freedom to build the sorted array directly from those tallies without ever pairing two values.

Take this basic example:

The next pass creates the sorted result without a single comparison.

This avoids stability handling, but it shows the concept with total clarity. Comparison based methods need decision making at every small turn, while counting sort moves with tally data alone. This difference places the method in a category where its speed depends on the data span far more than the number of elements.

Memory And Span Limits

Counting sort thrives when values fall into a narrow span. That’s because the method allocates a frequency array that covers the full distance from the smallest value to the largest one. A large span doesn’t always reflect how many numbers sit in the input, so it’s possible for the method to build a frequency array far bigger than the input itself. That mismatch can make other sorting methods a better pick for wide numeric ranges.

A short example builds out this scenario. Suppose a dataset holds a small set of values scattered across a large span:

If the code follows counting sort rules, the next step allocates based on the full span.

This array may cover thousands of slots even if the input holds only a handful of values. Counting sort still works, but the tradeoff becomes obvious. Memory use grows in direct relation to the numeric span, not the dataset size. Methods like mergesort avoid that tight bond because they never depend on knowing the numeric spread.

Still, when the value span stays small, counting sort moves fast and predictably. Its memory footprint remains compact, and the tallies build in a tight range that fits well with Java’s array behavior across all modern versions.

How Stability Matters For Later Steps

Stable ordering gives counting sort an advantage in workflows that depend on multi pass sorting. A stable method keeps the original order for values that match, which lets earlier ordering rules survive into later stages. That fact becomes vital in methods like radix sort, where the data moves through several passes that sort by individual digits or fields.

One common case shows how this property supports later passes. Suppose an object has two fields and the code sorts by the second field first, then by the first field. Stability makes that order stick.

The first pass can sort by grade through counting sort:

This counting pass by grade keeps the original order among items with grade 1. A later pass that sorts by group can then rely on the stable ordering to preserve the earlier placement tied to grade, giving a final result that reflects both fields in a predictable way.

Stability adds value without extra machinery. Counting sort secures that property through its backward placement step, and the effect ripples outward into later stages where ordering needs to flow from one rule into the next.

Comparison With Linear Time Relatives

Counting sort shares the linear time space with methods that also step around comparisons. Bucket sort spreads values across ranges, and radix sort breaks values into digits processed one level at a time. All three methods take advantage of structural clues in the input rather than comparisons.

Radix sort depends heavily on stability for accuracy. Counting sort often serves as a building block in that world, giving it a deeper place among non comparison sorts. One pass of radix sorting might call counting sort under the hood for a digit based sweep. Java code frequently pairs them in teaching and production settings because the two fit comfortably side by side in this structure.

A digit based pass can look like this:

The follow up prefix sweep and backward placement step mirrors counting sort’s structure. Radix sort evolves from this process by repeating passes at higher digit places.

Sorting with tallies holds a steady place in this group because it delivers linear performance when the span stays narrow and keeps stability without extra work. Its position feels natural among the small family of sorts that drop comparisons and rely on structure already present in the data.

Conclusion

Counting sort turns simple tallies into a full ordering of values without placing elements side by side for comparisons. Tallies guide the structure, prefix totals steer placements, and the backward pass keeps equal values in their original flow. All three pieces fit smoothly with modern Java and stay fast when the value span stays narrow. The method fits naturally in the family of non comparison sorts, supported by tallies, placement ranges, and stable movement from start to finish.

1. Java Arrays Documentation

2. Java Language Specification Section on Arrays

3. OpenJDK Source for Arrays Utility Methods

4. Oracle Java Tutorials on Data Structures