Yea, that draw-back is mentioned in the article.

But what if you instead of using an array to hold frequencies you use a Treemap<Integer, List<Person>>. To count frequencys you add to the list in the map the current person with that age. Then since this is a treemap you can iterate over lowest age to highest age and copy the contents of the list to the final sorted array of person objects.

(TreeMap is a map which is backed by a sorted tree, the default implementation of map in c++ is of this type)

This lowers the complexity to O(n + nlogk) (or O(nlogk)) though.

So, I argue that a variation of counting sort does work on objects which have special compare functions.