Как реализовать сортировку данных

Что проверяют

Понимание того, что именно делает стандартная библиотека, и умение собрать компаратор, не нарушив его контракт. Перечисление учебных алгоритмов тут закрывает вопрос только наполовину.

Как отвечать

Первое, что стоит сказать: в JDK две разные сортировки, и разница видна на практике.

• Arrays.sort(int[]) и прочие примитивы: dual-pivot quicksort, на месте, неустойчива (для примитивов устойчивость смысла не имеет). В современных JDK при плохом распределении происходит переключение на пирамидальную сортировку, поэтому квадратичной деградации нет.
• Arrays.sort(Object[]), Collections.sort, List.sort: TimSort, устойчивая, требует до O(n) дополнительной памяти и работает почти линейно на частично упорядоченных данных.

Устойчивость это не мелочь: именно она позволяет сортировать по нескольким критериям последовательными проходами, не теряя предыдущий порядок.

Компараторы собираются декларативно:

people.sort(
    Comparator.comparing(Person::lastName)
              .thenComparingInt(Person::age)
              .reversed()
);
list.sort(Comparator.comparing(Person::city, Comparator.nullsFirst(String::compareTo)));

comparingInt и thenComparingInt убирают автобоксинг на каждом сравнении, на больших списках разница заметна. nullsFirst и nullsLast нужны, когда поле может быть null: обычный компаратор упадёт с NPE.

Контракт компаратора: антисимметричность и транзитивность. Классическая ошибка это return a.age - b.age, где разность переполняется на больших значениях и порядок ломается. Правильно Integer.compare(a, b). TimSort проверяет контракт и при нарушении бросает IllegalArgumentException: Comparison method violates its general contract!, причём падает не всегда, а начиная с определённых объёмов данных, поэтому такой баг спокойно доживает до прода.

Comparable задаёт естественный порядок типа, Comparator внешний. compareTo должен быть согласован с equals, иначе TreeSet и TreeMap поведут себя не так, как HashSet.

Что ещё уместно упомянуть:

• Arrays.parallelSort для больших массивов, выигрыш начинается примерно от десятков тысяч элементов, ниже накладные расходы съедают его.
• stream().sorted() удобен, но для упорядоченного потока он обязан сохранять порядок и материализует данные; на горячем пути дешевле отсортировать список на месте.
• Нужны не все элементы, а top-K, берите PriorityQueue за O(n log k).
• Данные из базы сортируйте запросом по индексу, а не в памяти приложения.

Где спотыкаются

Перечисляют алгоритмы из учебника, но не знают, что для примитивов и объектов в JDK используются разные сортировки; пишут вычитание в компараторе и получают неверный порядок при переполнении.