ObjectCountingSort.java

Question

Intro

This time, I was in the mood for generalizing counting sort to arbitrary (Comparable) objects.

Code

io.github.coderodde.util.ObjectCountingSort.java:

package io.github.coderodde.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ObjectCountingSort {

    private ObjectCountingSort() {
        
    }
    
    public static <T extends Comparable<? super T>> 
    void sort(Collection<T> coll) {
    
        Map<T, List<T>> m = new HashMap<>();
        
        for (T elem : coll) {
            m.putIfAbsent(elem, new ArrayList<>());
            m.get(elem).add(elem);
        }
        
        List<T> keys = new ArrayList<>(m.keySet());
        Collections.sort(keys);
        
        coll.clear();
        
        for (T elem : keys) {
            coll.addAll(m.get(elem));
        }
    }
}

io.github.coderodde.util.demo.Demo.java:

package io.github.coderodde.util.demo;

import io.github.coderodde.util.ObjectCountingSort;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Demo {
    
    private static final int N = 1_000_000;

    public static void main(String[] args) {
        List<Integer> lst1 = new ArrayList<>(N);
        List<Integer> lst2 = new ArrayList<>(N);
        Random rnd = new Random();
        
        for (int i = 0; i < N; ++i) {
            Integer value = rnd.nextInt(N / 1000);
            lst1.add(value);
            lst2.add(value);
        }
        
        long ta = System.currentTimeMillis();
        ObjectCountingSort.sort(lst1);
        long tb = System.currentTimeMillis();
        
        System.out.println("OCS: " + (tb - ta) + " ms.");
        
        ta = System.currentTimeMillis();
        Collections.sort(lst2);
        tb = System.currentTimeMillis();
        
        System.out.println("JDK: " + (tb - ta) + " ms.");
        
        System.out.println("Algorithms agree: " + lst1.equals(lst2));
    }
}

Typical output

OCS: 152 ms.
JDK: 488 ms.
Algorithms agree: true

Critique request

Please, tell me whatever comes to mind.

(Just an idea: after 1st sqrt(coll.size()) items compare to m.size().) — greybeard
– greybeard, Commented Jan 25 at 20:51

Jörg W Mittag · Accepted Answer · 2026-01-26 15:16:20Z

Counting Sort

This time, I was in the mood for generalizing counting sort to arbitrary (Comparable) objects.

This is not possible. Counting sort requires that the sort keys be "small" positive integers. You cannot sort arbitrary objects with counting sort, even if you restrict them to be comparable.

Note: the objects themselves don't have to be small positive integers, but the sort keys have to be, or at least have to map to a finite set of small positive integers.

`Comparable`

Ironically, given I wrote above that you are being too general, you are also needlessly restricting your input: there is no requirement that the elements being sorted by counting sort are Comparable. In fact, the whole point of counting sort is that it is not a comparison sort, i.e., that it is not based on comparisons. Equality is all you need. (Obviously, the sorted output induces a mathematical comparison relation over the input, but it is not an a priori requirement for the actual implementation of the algorithm that the objects implement the Comparable interface.)

The fact that counting sort is not a comparison sort and does not use comparisons means that it is not subject to the \$\mathcal{\Omega(n \log{}n)}\$ lower bound of comparison sorts. In fact, counting sort's worst-case asymptotic step complexity is \$\mathcal{O(n+k)}\$, as is its worst-case asymptotic space complexity, where \$\mathcal{k = key_{max}-key_{min}}\$.

That asymptotic bound is a key ingredient of what makes counting sort a counting sort, and would probably be one of the major reasons why someone would choose a counting sort. (For some interesting thoughts on what it means for a program to be a genuine implementation of an algorithm, I can highly recommend Melissa E. O'Neill's The Genuine Sieve of Eratosthenes.)

API documentation

There is no API documentation in your code. Regardless of whether you actually meant to implement a genuine counting sort or not, this code needs documentation:

If this were a genuine counting sort, the requirements for the elements of the collection must be documented, since they cannot be (easily) expressed in the Java type system.
Since this is not a genuine counting sort, it really should be documented that it is not a genuine counting sort, especially since it has counting sort in the name.
One of the major reasons for choosing one sorting algorithm over another are the various performance and stability guarantees the algorithm gives as well as the overhead of the particular implementation. In this case, the sort is:
- stable,
- not-in-place, and
- the worst-case asymptotic step complexity looks to be \$\mathcal{O((n+c) \log{}c)}\$, where \$c\$ is keys.size().
Your algorithm requires the elements to be both comparable and hashable. Comparable is called out in the type signature, but hashability is not mentioned. Of course, in Java, all objects are hashable, but a user will likely not expect a sort method to require hashing, therefore, it should be explicitly called out.

Naming

Since this is not, in fact, a counting sort, I would refrain from using "counting sort" anywhere in the name.

Benchmarking

As already mentioned in other answers, your benchmark methodology leaves something to be desired. I will not critique the benchmark in detail, but instead offer some more general advice:

Benchmarking is hard. Really hard. It requires above-average knowledge of programming language pragmatics (e.g., high-level and low-level compiler optimizations, runtime internals, memory allocation and management, etc.), computer organization and implementation (memory hierarchy, caching and cache coherency, etc.), CPUs (ISAs, microarchitectures, optimizations, bottlenecks, etc.), statistics, and probably dozens of other things I forget. Benchmarks are generally written by entire teams of people with lots of experience, for whom writing benchmarks is their full-time and only job … and they still get it wrong sometimes.

Some (in)famous benchmark mistakes that actually happened in industrial, peer-reviewed benchmarks:

Writing the benchmark in such a way that the compiler recognized that the result of the benchmark was never used and thus optimized the entire benchmark away.
Writing the benchmark in such a way that the compiler recognized that the benchmark result was independent of the benchmark loop and thus hoisted the benchmark outside of the loop and only executed it once.
Writing a SQL database benchmark that was so trivial that the benchmark actually just measured how fast the memory allocator of the JVM could allocate the java.sql.ResultSet objects.

In fact, you did not just write the benchmarks, you also wrote the benchmark harness, i.e., the code which wraps around the benchmarks, manages their lifecycle, performs the measurements, collects the results, minimizes interference, etc. That is even harder than just writing the benchmarks. I encourage everyone who writes benchmarks and/or harnesses to read (and understand!) the mailing list thread on the Mechanical Sympathy mailing list starting at https://groups.google.com/g/mechanical-sympathy/c/m4opvy4xq3U/m/7lY8x8SvHgwJ.

Just to point out one example: almost all JVMs have a profiling period before they actually perform any optimizations. For Oracle's OpenJDK in server mode and in the default configuration, it does not even compile a method until the method has been executed 20000 times. Your sort method is only executed once, so it will not be optimized, unless you really force the JVM with a barrage of command line arguments. And even then, you will need many measurements to filter out measurement noise, run-to-run variations, etc.

Another problem with your benchmarks is that they are not repeatable. I cannot run the benchmark and compare my results to yours, because I do not know the random seed you used to generate the input list.

See also Idiomatic way of performance evaluation?. But yeah, Java is probably one of the hardest high-performance languages to microbenchmark since it doesn't have anything like volatile, and is JIT-compiled, so JMH really has a hard task. Thanks for the JMH groups link, sounds pretty impressive that they're able to take care of so many pitfalls. (One quibble though: the other thing you can measure besides throughput is latency, by making a loop where the input for the next iter depends on output of previous. Matters for very short ops w. OoO exec.) — Peter Cordes
– Peter Cordes, Commented Jan 29 at 1:58

Chris · Accepted Answer · 2026-01-26 15:52:01Z

Data collection

As I have mentioned several times on similar posts, you're comparing a single run of both methods. You would be better served by a more scientific approach: gather more data, and account for more variables.

How do different sized data sets compare?
- Small sets
- Medium sets
- Large sets
You've generated random data. How do both do with data that's not entirely random?
- Sorted already
- Almost sorted
- Reversed
What happens if all of the elements of the collection to be sorted are unique?
What happens if you try something other than integers?
- Or integers across a very large range? (It's not difficult to predict: Counting sort at Wikipedia

Your results, as they exist now suggest your sort is much faster than the standard library's. This isn't necessarily impossible, but it should raise serious questions. And getting more questions from an experiment is a good thing as long as your aim is computer science and not computer engineering.

Aesthetics

From a purely style standpoint, you may wish to use System.out.printf as opposed to manual concatenation.

        long ta = System.currentTimeMillis();
        ObjectCountingSort.sort(lst1);
        long tb = System.currentTimeMillis();
        
        System.out.println("OCS: " + (tb - ta) + " ms.");
        
        ta = System.currentTimeMillis();
        Collections.sort(lst2);
        tb = System.currentTimeMillis();
        
        System.out.println("JDK: " + (tb - ta) + " ms.");
        
        System.out.println("Algorithms agree: " + lst1.equals(lst2));

Becomes:

        long ta = System.currentTimeMillis();
        ObjectCountingSort.sort(lst1);
        long tb = System.currentTimeMillis();
        
        System.out.printf("OCS: %dms.\n", tb - ta);
        
        ta = System.currentTimeMillis();
        Collections.sort(lst2);
        tb = System.currentTimeMillis();
        
        System.out.printf("JDK: %dms.", tb - ta);
        
        System.out.printf("Algorithms agree: %b\n", lst1.equals(lst2));

Spoiler alert: a standard histogram is slower on sorted input since you end up storing/reloading the same counter repeatedly in one long dependency chain, instead of having multiple separate load/increment/store dep chains in parallel. If the value-range is small enough, it's cheap to mitigate this by unrolling over multiple arrays of counters, and summing at the end. If the value-range is not small, multiple maps get expensive to allocate and to merge at the end, so you'd only do that if multithreading (giving each thread its own map). — Peter Cordes
– Peter Cordes, Commented Jan 29 at 2:05

greybeard · Accepted Answer · 2026-01-25 22:28:51Z

Not using the return value of putIfAbsent() relies on intelligence on the JIT's side.

        for (T elem : coll)
            putIfAbsent(elem, new ArrayList<>()).add(elem);

This instantiates a lot of ArrayLists without specifying a size. The docs suggested

        for (T elem : coll)
            computeIfAbsent(elem, k -> new ArrayList<>()).add(elem);

Then, there is <T,K> Collector<T, ?, Map<K, List<T>>> Collectors.groupingBy(Function<? super T, ? extends K> classifier) - unchecked, out of my depth here:
m = coll.stream().collect(Collectors.groupingBy(Function<>.identity));
Even sort on the go using
Collectors.groupingBy(Function<>.identity, TreeMap<>::new, Collectors.toList())

\$\begingroup\$ (Have I given up preaching doc comments?) \$\endgroup\$

greybeard
– greybeard

2026-01-25 22:31:18 +00:00
Commented Jan 25 at 22:31 — greybeard
– greybeard, Commented Jan 25 at 22:31

Stack Exchange Network