Как вы считаете, если выполнить java.util.Arrays.sort(), то какая сортировка будет вызвана? Quicksort? Timsort? И та, и другая, потому что для объектов вызывается Timsort, а для примитивов (чисел int, long, float и так далее) — Dual-Pivot Quicksort. В JDK 6 для объектов использовался стандартный Merge sort, а для чисел классическая реализация Quicksort с одним опорным элементом, предложенная Джоном Бентли и Дугласом МакИлрой. В JDK 7 оба алгоритма поменялись: теперь объекты сортируются с помощью Timsort, автор Тим Петерс, а для простых типов данных используется Dual-Pivot Quicksort, предложенный мною вместе с Джоном Бентли и Джошем Блоком в 2009 году. Эта сортировка используется более 15 лет не только в JDK, но и в Android (хотя и немного устаревшая версия).

А зачем нам вообще второй алгоритм сортировки, если есть Timsort? Почему не использовать один и для объектов, и для примитивов? Сегодня я, как автор, расскажу историю Dual-Pivot Quicksort: как он начинался, как развивался и как продолжает развиваться сейчас.

Timsort

В 1993 году Питер МакИлрой показал, как можно улучшить Merge sort на упорядоченных или почти упорядоченных данных. Через 9 лет Тим Петерс реализовал его идею в Python и назвал эту сортировку в честь себя — Timsort. Позже Джош Блок портировал этот алгоритм в JDK 7. 

Давайте вспомним, как работает Merge sort, на котором основан Timsort. Мы делим массив пополам, каждую часть сортируем рекурсивно и потом обе части сливаем обратно в массив. Timsort работает немного иначе:

  • на каждом шаге ищутся возрастающие и убывающие подпоследовательности;

  • убывающие переворачивается (и делаются возрастающими);

  • короткие расширяются сортировкой вставками до некой минимальной длины;

  • и на каждой итерации подпоследовательности сливаются обратно в исходный массив.

Сравненим Timsort и Merge sort на тестовом наборе из 1 миллиона элементов, предложенном Джоном Бентли. Timsort показывает исключительную скорость на периодических данных, почти упорядоченных и просто упорядоченных:

Каждый набор имеет какое-то количество модификаций, и при построении массива используется несколько параметров. Сравниваемые алгоритмы запускаются на всевозможных комбинациях и на различных платформах.

Dual-Pivot Quicksort

Классический Quicksort работает очень просто:

  • выбирается один элемент, называемый опорным;

  • все элементы перегруппируются следующим образом: те, что меньше опорного элемента, переносятся в левую часть, большие — в правую, элементы, равные опорному, могут идти куда угодно;

  • далее каждая часть сортируется рекурсивно.

А что если взять два опорных элемента (предполагается, что первый не больше второго), и перегруппировать аналогичным образом на три части?

Эта идея не нова. Ещё в конце 1970-х Роберт Седжвик в своей диссертации исследовал сортировку с двумя опорными элементами. По его расчётам, этот вариант по количеству обменов проигрывает классическому более чем в 2,5 раза. На основании этого Седжвик сделал вывод о неперспективности этой сортировки и прекратил её исследование.

Но я об этом не знал, и когда в 2008 году мне пришла в голову идея с двумя опорными элементами, проверил ее сначала на списках, потом в конце года написал первую черновую версию для массивов. Она была всего лишь на 5 % быстрее, чем сортировка в JDK 6. Весной 2009 года я начал обсуждать идею с Джош Блоком, летом улучшил алгоритм. В то же время Джош Блок написал Джону Бентли, автору сортировки в JDK 6, о том, что есть новая сортировка, от результатов которой невозможно отмахнуться. Бентли сделал ревью моего кода, дал ценные советы, и в сентябре появилась новая сортировка под названием Dual-Pivot Quicksort. Потом Джош Блок помог мне её интегрировать в JDK (сейчас процесс интеграции в OpenJDK стал прозрачнее, но об этом мы поговорим ниже).

С момента интеграции я неоднократно улучшал свой алгоритм, делал его всё быстрее и быстрее.

Сравнение на тестовом наборе Джона Бентли, можно сказать, что текущая версия работает быстрее сортировки из JDK 6 на всех типах данных.

Dual-Pivot Quicksort изнутри

Сортировка небольших массивов

Почему очень важно уметь сортировать небольшие массивы? Если исходный массив большой, то Quicksort рекурсивно разбивает его на много маленьких кусочков, которые потом сортирует. Известно, что сортировать несколько десятков элементов быстрее не рекурсивным Quicksort, а сортировкой вставками: алгоритм на каждом шаге берёт очередной элемент и вставляет в отсортированную часть.

for (int j, i = left+1; i <= right; ++i) {
  int ai = a[i];
  for (j = i–1; /* j >= left && */ ai < a[j]; --j) {
    a[j+1] = a[j];
  }
  a[j+1] = ai;
}

Обратите внимание, что во внутреннем цикле есть проверка, не выходит ли индекс j за левую границу. Условие вычисляется каждый раз, но в большинстве случаев не срабатывает. Можно ли как‑то избавиться от этой дорогой проверки?

Если посмотреть на сортировку вставками в контексте Quicksort, то заметим, что первый опорный элемент P1 по условию не превосходит любого элемента из средней части, так что условие /* j >= left && */ мы можем просто выкинуть для любой части кроме самой левой. А для левой можно применить обычную сортировку вставками.

А если для сортировки вставками воспользоваться идеей «один хорошо, а два лучше»? Мы получим так называемую парную сортировку вставками: за одну итерацию вставляются сразу два элемента. Сначала вставляется больший, а потом с его позиции ищется место для меньшего. Таким образом уменьшается количество сравнений и обменов, что приводит к увеличению скорости.

Опорные элементы

Quicksort — уникальный алгоритм, в котором нет чётких указаний, как выбирать опорный элемент. Какой способ придумаете, такой Quicksort и получите. Quicksort с одним опорным элементом работает хорошо, с двумя — лучше. Я пробовал с тремя, но получилось хуже. Какое же количество оптимальное? С точки зрения количества обменов и сравнений — 1,6180339... Это ни что иное, как «золотое сечение». Его используют в архитектуре, живописи, фотографии и т. д. Оно повсюду встречается в природе. Например, в качестве опорных элементов можно выбирать:

  • случайные элементы;

  • средние или крайние;

  • медиану медиан.

Допустим, есть у нас девять элементов. Делим их на тройки, в каждой из них выбираем средний элемент, из средних выбираем ещё раз средний.

Экспериментально удалось определить, что лучше всего брать 5 равноудалённых от центра элементов, отсортировать их и принять в качестве опорных первый и последний элементы.

——————— [1] — [2] — [3] — [4] — [5] ———————

  +шаг           середина            -шаг

На каком расстоянии должны стоять наши элементы?

шаг = длина * 0,381966 // делим в «золотом сечении»

Но умножение на вещественное число лучше заменить дешёвой аппроксимацией с помощью сдвигов вправо:

шаг = (длина >> 2) + (длина >> 3) + (длина >> 7)

Казалось бы, отсортировать 5 элементов очень просто. Но как именно это сделать? Можно применить сортировку вставками, но тогда мы получим 10 сравнений. Есть более эффективный способ для работы с небольшими количествами элементов — сети сортировки. Для 5 элементов они дают 9 сравнений. Мелочь, а приятно.

Разбиение массива

Если опорные элементы различаются, мы делим массив на три множества. Если опорные элементы равны, то среднее множество содержит одинаковые элементы. Получается, что оно уже отсортировано и его можно исключить из дальнейшего рассмотрения.

В этом случае получается разбиение из задачи о национальном флаге. Попробуйте ее решить на Leetcode. Удивительный факт: классический Quicksort с одним опорным элементом на периодических данных работает примерно на 35-65% быстрее двухопорного. И хотелось бы этим свойством как-то воспользоваться. Поэтому применим такую эвристику: будем переключаться на разбиение с двумя опорными элементами только тогда, когда все кандидаты в опорные элементы различны. Таким образом, на разных данных количество опорных элементов будет один или два, в среднем как раз и получим «золотое сечение».

Сортировка почти упорядоченных данных

Как я уже отмечал, Timsort показывает исключительную скорость на почти упорядоченных данных. Как применить это к числам? Находим возрастающие и убывающие последовательности, убывающие переворачиваем в возрастающие, потом всё собираем в единый отсортированный массив. Очень похоже на Timsort, но есть существенное отличие: Timsort сканирует весь массив, а мы будем это делать, только если количество множеств не превысит какого-то порога. Quicksort не обязан быть стабильным, то есть может менять порядок одинаковых элементов (для чисел это не актуально), поэтому допустимо нестрогое возрастание и нестрогое убывание:

a[k] <= a[k + 1] <= a[k + 2] <= ... <= a[m]

a[k] >= a[k + 1] >= a[k + 2] >= ... >= a[m]

К тому же короткие последовательности мы не расширяем.

Отметим оптимизации, связанные с памятью. Во-первых, мы запрашиваем под буфер «грязную» память, которая может быть не обнулённой, потому что мы сначала записываем в буфер, а потом читаем. Отказавшись от обнуления, мы немного выигрываем в скорости. А во-вторых, если массив большой и памяти не хватает, мы не вылетим с ошибкой OutOfMemory, а переключимся на inline-алгоритмы, не требующие дополнительной памяти. То есть сортировка в любом случае завершится корректно.

Сортировка вещественных чисел

Как вы думаете, если два элемента равны, должны ли они идентично представляться в памяти? Или обратный вопрос: если элементы не равны, должны ли их представления в памяти быть различными? В математике оба ответа — «да». А в Java — «нет», потому что в мире Java есть две аномалии: -0, который не равен 0, и NaN, который не равен никому, даже самому себе. Поэтому с точки зрения JavaDoc порядок вещественных чисел должен быть такой:

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

  1. переместить все NaN’ы в конец массива;

  2. отсортировать оставшиеся элементы;

  3. переместить -0.0 перед 0.0, зная что:

    1. Float.floatToRawIntBits(0.0) == 0

    2. Float.floatToRawIntBits(-0.0) < 0

Или можно поступить иначе:

  1. переместить все NaN’ы в конец массива, посчитать количество -0.0 и заменить их на 0.0;

  2. отсортировать оставшиеся элементы;

  3. заменить нужное количество первых 0.0 на -0.0.

Второй алгоритм сейчас используется в JDK.

Параллельная сортировка

В Java есть пакет java.util.concurrent, который предоставляет много всего полезного. Но мы параллельную сортировку писать не будем, потому что она уже есть: начиная с восьмой версии появился метод Arrays.parallelSort(), который основан на сортировке слиянием и подходит как для объектов, так и для чисел.

Казалось бы, если Quicksort быстрее, чем MergeSort, то было бы логично использовать Arrays.parallelSort() тоже на основе Quicksort. Но если мы возьмём мощный сервер с большим количеством процессоров, то параллельный MergeSort будет работать быстрее. Поэтому, начиная с 14 версии, используется гибрид. В зависимости от количества процессоров и размера массива какое-то количество раз вызывается параллельная сортировка слиянием, а потом переключаемся на Quicksort.

Сортировка чисел

Я уже много рассказал про Quicksort, наверное, это самая быстрая сортировка со сложностью O(n*ln(n))? Давайте посмотрим на такой массив: 0 1 0 1 0 2 1 0 1 1 0 2 1 1 0 0 1 2 0 0. Как его сортировать? Просто посчитаем количество нулей, единиц и двоек, а потом запишем их подряд: 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2. Это сортировка подсчётом, которая имеет линейную сложность, а не n*ln(n), как Quicksort. Сортировка подсчётом используется в JDK для сортировки byte, char и short.

Хотелось бы воспользоваться этой идеей для более широкого диапазона, int и long. Для этой цели есть поразрядная сортировка (Radix sort): сначала сортируем числа по одному разряду, потом по следующему, и так далее.

Heap sort

Однажды мне написал программист и пожаловался, что на соревнованиях по спортивному программированию его команда проиграла. В спортивном программировании программа должна работать не только правильно, но и как можно быстрее. Изюминка того соревнования была в том, что тестовые данные могло давать и жюри, и соперники. Эти участники знали версию JDK и что там используется Quicksort. А для любого Quicksort можно подобрать данные так, что алгоритм сортировки покажет квадратичное время. И в результате команда написавшего мне человека проиграла. Я пообещал, что исправлю это. Так появился Heap sort. Как и Quicksort, он работает за O(n*ln(n)), не требует дополнительной памяти.

Вот набор алгоритмов, работающих под капотом Dual-Pivot Quicksort:

Сравнение Timsort с Quicksort

Timsort:

  • идеален для сортировки объектов;

  • он стабильный, то есть не меняет порядок одинаковых элементов;

  • использует дополнительную память;

  • имеет сложность O(n*ln(n)) во всех случаях.

Классический Quicksort:

  • для сортировки простых типов;

  • сортирует «на месте»;

  • не требует дополнительной памяти;

  • нестабильный, то есть может менять местами одинаковые элементы, но для чисел это не актуально;

  • имеет сложность:

    • O(n*ln(n)) в наилучшем случае;

    • O(n*ln(n)) в среднем случае;

    • O(n^2) в наихудшем случае.

Что изменилось в JDK 14: Quicksort использует дополнительную память и имеет сложность:

  • O(n) в наилучшем случае (с помощью Merging sort);

  • O(n*ln(n)) в среднем случае;

  • O(n*ln(n)) в наихудшем случае (с помощью Heap sort).

Поскольку Timsort стабильный, его нельзя заменить для сортировки объектов на нестабильный Quicksort. Этого требует спецификация: не имеет значения, какой применять алгоритм, важно, чтобы он был стабильным.

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

Если мы покопаемся в исходниках класса Arrays.java, то найдём старую сортировку слиянием. Почему она там осталась? Timsort — довольно продвинутый алгоритм, он может обнаружить некорректную реализацию comparable или comparator и выкинет исключение «Comparison method violates its contract». Но если это произойдёт в промышленной эксплуатации, то она упадёт. Чтобы этого не произошло, есть флаг «использовать merge sort».

Какая сортировка самая лучшая?

Ответ зависит от многих факторов:

  • Какой размер массива?

  • Можем ли использовать дополнительную память?

  • Требуется ли гарантированная сложность O(n*ln(n))?

  • Нужна ли устойчивость?

  • Проверяем ли правильность сравнения?

  • Знаем ли мы природу элементов?

  • Насколько данные уже упорядочены?

Какая сортировка самая лучшая? Если отвечать кратко, то это реализация в классе java.util.DualPivotQuicksort, там всё самое лучшее. Под капотом у него целый зоопарк разных алгоритмов:

Тестирование сортировки

Timsort, как и наш мир, не идеален. В 2015 году система верификации KeY нашла в нем алгоритмическую ошибку. Сначала подумали, что это ошибка в самой системе, но нет. Сначала сделали простенькое исправление, но алгоритмически код оставался неверным, хотя она не воспроизводилась в рамках JVM. И только в 2018-м сделали правильное исправление алгоритма.

Quicksort оказался не лучше, и с JDK 8 по JDK 13 параллельная сортировка вещественных чисел Arrays.parallelSort() неправильно сортировала -0 и NaN. Эта ошибка была исправлена в JDK 14.

Какой тест можно написать для сортировки? Например, проверить, что каждый следующий элемент не меньше предыдущего: a[0] <= a[1] <= … <= a[n – 1] <= a[n]. Но представим, что у нас есть вот такая хитрая сортировка, которая просто обнуляет массив:

void sort(int[] a) {
  for (int i = 0; i < a.length; ++i) {
    a[i] = 0;
  }
}

И такая реализация пройдёт наш тест! Поэтому нужно придумать более надёжные проверки. Например, возьмём два одинаковых неотсортированных массива, отсортируем их разными алгоритмами и сравним результаты. Идея хорошая, но годится только для небольших массивов, потому что на больших данных некоторые алгоритмы работают очень долго.

Можно поступить иначе. Возьмём упорядоченный массив, перемешаем элементы, отсортируем и сравним с эталоном. Тоже хорошая идея.

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

Сортировка данных разных типов

Вот сравнение сортировки 60 000 случайных чисел в разном представлении:

Списки сортируются гораздо дольше, чем массивы объектов, потому что список сначала конвертируется в массив, сортируется, а потом конвертируется обратно. Объекты Integer сортируются медленнее, чем int, поэтому если у вас есть Integer, то выгоднее преобразовать его в int и отсортировать. Тип short сортируется гораздо быстрее, потому что используется сортировка подсчётом.

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

Статьи про Dual-Pivot Quicksort

Через несколько лет после выхода JDK 7 в интернете стали появляться статьи с анализом моей сортировки, например:

  • «Holistic Analysis of Yaroslavskiy's Partitioning Scheme», Markus E. Nebel and Conrado Martinez, Dept. of Computer Science, Univ. Politecnica de Catalunya

  • «Dual-Pivot Quicksort», Vasileios Iliopoulos and David B. Penman, Department of Mathematical Sciences, University of Essex

  • «Average Case Analysis of Java 7's Dual Pivot Quicksort», Sebastian Wild and Markus E. Nebel, Computer Science Department, University of Kaiserslautern

Вот, например, автор Себастьян Уайлд сначала в своей дипломной работе исследовал Quicksort, потом диссертацию написал, издал две книги, но ответа нет до сих пор.

Проект OpenJDK

Вы можете внести свой вклад в развитие OpenJDK. Заходите на страничку, выбирайте интересующую группу, смотрите список открытых багов, текущих задач, пишите и тестируйте свой лучший код.

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

Могу сказать лишь, что очень тяжело улучшить чужой код, а улучшить свой код, да еще несколько раз, — нереальная задача. И всё же сортировка продолжает развиваться:

Выводы

  • Пробуйте, пробуйте и не бойтесь что-либо делать.

  • За прошедшие годы сортировка всё время улучшалась и продолжает улучшаться.

  • Интегрироваться в OpenJDK не страшно.

  • Java — это не то же самое, что математика.

  • Тесты спасают наш мир!

Полезные ссылки

Владимир Ярославский

Руководитель направления, Сбер