Я не java разработчик а python и c++. Считаем теоретическую сложность. Пробежаться и посчитать сколько каждое число встречается это O(n). Вывести результат это тоже будет O(n). И того O(2n) => сложность O(n). Но это при условии что нет коллизии. Для этого заранее можно выделить размер под 1 миллиард переменных. Поэтому я и сказал, что проигрываем по памяти, а по скорости O(n) вместо O(nlogn).
Можно ещё быстрее. Подсчитаем сколько раз каждое число встречается в массиве. А затем просто в цикле от 0 до 1 миллиарда будем проверять входит ли i в map и если да то выводим i ровно map[i] раз.
Есть какие нибудь планы по поддержки redis?