Лекция 11. Современные сортировки

Все программисты знают, что такое сортировка. Все когда-то изучали сортировку пузырьком, многие — QuickSort, а кто-то знает и HeapSort. Но как ни крути, эти сортировки были придуманы слишком давно и часто не удовлетворяют современным требованиям.

На лекции мы разберём, как нужно сортировать в 2020 году. Поймём, как работает TimSort — сортировка, используемая в питоне и джаве. Разберём задачу параллелизации сортировки — как быстро вы можете отсортировать массив чисел, если у вас есть 32 ядра? А если 128 ядер? Обязательно поговорим про ARL — быструю кеш-френдли сортировку «на месте».

Субъективная сложность лекции — две теты из пяти.

00:07:06 - Классические алгоритмы сортировки, квадратичные и логарифмические
00:21:00 -TimSort
00:38:55 - Дополнительные оптимизации TimSort. Галоповый поиск
01:02:00 - Поразрядная сортировка
01:11:00 - Adaptive Left Radix Sort
01:17:35 - Параллельные алгоритмы сортировки. Сортирующие сети.
01:27:40 - Bitonic Sort
01:38:00 - Сортировка на GPU. Warp-Based Bitonic Sort

Видео Лекция 11. Современные сортировки канала Технологии в Контуре