Владимир Ярославский. Удивительная история развития сортировки в JDK

Владимир Ярославский Руководитель направления, Сбер Удивительная история развития сортировки в JDK С момента появления JDK для сортировки простых типов использовалась классическая (с одним опорным элементом) быстрая сортировка (Quicksort). В ноябре 2009 года в JDK 7 появился предложенный докладчиком улучшенный алгоритм быстрой сортировки Dual-Pivot Quicksort, который в 1,5–3,5 раза быстрее предыдущей версии. Тогда же и Timsort заменил Merge sort для сортировки объектов. За последние 14 лет Dual-Pivot Quicksort неоднократно улучшался по сравнению с первоначальной версией. Какие оптимизации и приёмы использовались? Как повышалась производительность? Как правильно тестировать сортировку? Планируется обсудить эти и многие другие вопросы. Доклад заинтересует не только разработчиков, но и математиков, любителей алгоритмов, тестировщиков, аналитиков, а также всех тех, кто стремится к ещё более эффективному коду и кто хочет внести свой вклад в развитие JDK.