Java Puzzle 65: A Strange Sage of a Suspicious Sort

Всю программу приводить не буду. Приведу пример неправильной реализации компаратора, из-за которого вся программа сортировки работает неправильно.
class IntegerComparator implements Comparator {
    public int compare(Integer i1, Integer i2) {
        return i2 - i1;
    }
}
Идиома, лежащая в основе этой имплементации, известна с ранних дней UNIX (1970). Поэтому многие уже не помнят, а остальные не знают, решение этой проблемы. Помните, что компьютерная математика отличается от обычной. И при вычитании большого положительного числа из большого отрицательного числа можно получить положительное, а не отрицательное. Это называется - переполнение разрядной сетки...
Вот правильная имплементация:
class IntegerComparator implements Comparator {
    public int compare(Integer i1, Integer i2) {
        if (i1 > i2) return -1;
        if (i1 < i2) return 1;
        return 0;
    }
}
После анализа кода становится ясно, что этот компаратор предназначен для сортировки в обратном порядке. Так что не надо городить своих классов. Используйте компаратор, входящий в состав библиотеки коллекций:
Collections.reverseOrder()