Сортировка в Java

В стандартной библиотеке Java существует три группы перегруженных методов для сортировки:

1. java.util.Arrays.sort(prim[], ...) — для сортировки массивов примитивов prim (int, byte, char, и т.д.). Использует алгоритм быстрой сортировки (quick sort).
2. java.util.Arrays.sort(T[], ...) и java.util.Arrays.sort(Object[], ...) — для сортировки массивов комплексных объектов произвольного типа T или Object. Использует алгоритм сортировки слиянием (merge sort).
3. java.util.Collections.sort() — для сортировки коллекций. Использует алгоритм сортировки слиянием (merge sort).

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

(4, 2)  (3, 7)  (3, 1)  (5, 6)

Тогда на выходе, в зависимости от использованного алгоритма сортировки, мы можем получить два различных результата:

(3, 7)  (3, 1)  (4, 2)  (5, 6)   (порядок сохранен)
(3, 1)  (3, 7)  (4, 2)  (5, 6)   (порядок изменен)

В первом случае пары (3, 7) и (3, 1) с равными ключами сортировки остались в том же порядке следования, как и изначально. Во втором случае они поменялись местами.

Почему важна устойчивая сортировка? Она позволяет производить цепочку последовательных сортировок, добиваясь сортировки в группах и подгруппах коллекции. Покажем, что это означает, на примере (примеры записаны на языке Scala для минимизации избыточного кода, присущего Java, но смысл будет ясен). Пусть мы имеем структуру данных для представления музыкальных записей:

// `albumName` - имя музыкального альбома;
// `trackNumber` - номер трека в альбоме.
case class Record(albumName: String, trackNumber: Int)

Разместим в списке несколько музыкальных произведений (из дискографии группы Metallica) в произвольном порядке:

val records = List(Record("Master of Puppets", 7), Record("Load", 4),
                   Record("Load", 2), Record("Reload", 5),
                   Record("Load", 3), Record("Reload", 3))

Теперь отсортируем записи по номеру трека:

scala> val byTrackNumber = records.sortBy(_.trackNumber)
byTrackNumber: List[Record] = List(Record(Load,2), Record(Load,3), Record(Reload,3), Record(Load,4), Record(Reload,5), Record(Master of Puppets,7))

А затем отсортируем еще раз, но уже по имени альбома:

scala> byTrackNumber.sortBy(_.albumName)
res4: List[Record] = List(Record(Load,2), Record(Load,3), Record(Load,4), Record(Master of Puppets,7), Record(Reload,3), Record(Reload,5))

Что мы получили? Мы получили список записей, отсортированный по имени альбома, а в каждом альбоме отсортированный по номеру трека! Для этого мы сначала применили сортировку по менее значимому ключу (номер трека), которая сортирует для нас записи в подгруппах (альбомах). Затем сортировку по более значимому ключу - имени альбома. Такая последовательность важна. Следует заметить, что этот результат можно было бы получить, если сразу отсортировать записи по альбому И номеру трека за один раз, но существуют ситуации, когда нам неизвестны заранее все ключи, по которым мы будем сортировать коллекцию. К примеру, пользователь программы может выбрать в графическом интерфейсе сначала сортировку по полю "номер трека", а только затем по полю "альбом".

В случае, если бы мы применили нестабильную сортировку, вышеуказанный результат не гарантирован. Почему тогда для сортировки примитивов используется быстрая сортировка, являющаяся неустойчивой? Потому что равные примитивы (числа, символы) неотличимы друг от друга при перестановке, в отличие от комплексных объектов. Иными словами, примитивы можно сортировать только по одному ключу (их значениям). Поэтому для них допустимо применить более быстрый алгоритм, коим и является быстрая сортировка.