Турнир сортировок

В прошлой главе обход в ширину нашёл в метро путь с наименьшим числом перегонов. Навигатору этого мало: у дорог есть длина, а BFS её не видит. Прежде чем учить машину взвешивать дороги, нужны два умения, на которых держится почти любая программа с данными, навигатор в том числе: быстро найти и упорядочить. Улицу среди сотен тысяч названий навигатор находит за миг, потому что названия лежат по алфавиту, а маршруты выдаёт от быстрого к медленному — их он тоже сортирует. Эта глава — турнир. Участники выходят на ринг по очереди, у каждого — счётчик сравнений, а в конце судья объявит предел, через который не перепрыгнет никто. Первым выходите вы.

Раунд первый: человек

Перед вами пять карт рубашкой вверх. На каждой написано число, но переворачивать карты нельзя. Можно указать на две и спросить судью, на какой из них число больше. Каждый такой вопрос — одно сравнение, и счётчик их считает. Задача — узнать, в каком порядке лежат числа, задав как можно меньше вопросов. Чтобы не держать ответы в голове, карты можно передвигать пальцем или мышью, раскладывая их по своей догадке: перекладывать бесплатно, платят только вопросами.

Сколько вопросов у вас ушло? Девять или десять — обычный результат первой партии, восемь — хороший. Сыграйте ещё пару раз: удастся ли уложиться в семь?

Следите за полоской под картами. Пять разных чисел можно разложить в ряд $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ способами (откуда берётся факториал, рассказано в «Царице наук»), и в начале игры возможен любой из них. Каждый ответ судьи вычёркивает порядки, которые ему противоречат. Удачный вопрос вычёркивает половину, неудачный — меньше. А бывает, что вопрос не вычёркивает ничего: его ответ следовал из прежних, и сравнение потрачено впустую. Игра кончается, когда остаётся один-единственный порядок, — тогда карты открываются.

После партии под полоской появится счёт: сколько сравнений на этой же колоде сделали бы алгоритмы, которые выйдут на ринг следом. Человек — сильный игрок: он помнит все ответы и на ходу придумывает хитрые вопросы. Но на миллион карт у человека не хватит терпения. Алгоритму терпения не занимать, зато придумывать он не умеет и только выполняет правило. И, как и вы, о данных он узнаёт только из сравнений: каждое отвечает на вопрос «меньше или нет», и больше ничего. Посмотрим, каких правил хватает машинам.

Раунд второй: выбор

Первая стратегия — та, которой выстраивают по росту класс на физкультуре: найти самого низкого и поставить первым, потом самого низкого из оставшихся — вторым, и так до конца. Это сортировка выбором. Под ячейкой появится ползунок, и кадр за кадром будет видно, как растёт готовая часть.

Сколько здесь сравнений? Чтобы найти наименьший из $n$ элементов, кандидата надо сравнить с каждым из остальных — это $n - 1$ сравнение. Потом наименьший из $n - 1$ оставшихся — ещё $n - 2$, и так далее:

$$(n-1) + (n-2) + \ldots + 2 + 1 = \frac{n(n-1)}{2}.$$

Ровно столько пар можно составить из $n$ элементов, хотя перебирает выбор не пары: он сравнивает каждый элемент с текущим кандидатом, и на списке [2, 3, 1] пару 2 и 3 сравнит дважды, а пару 1 и 3 — ни разу. Тысяча чисел — почти полмиллиона сравнений, миллион — полтриллиона. На пяти картах выбор задаёт десять вопросов, и вы, скорее всего, его уже обыграли. Хуже того, это число не зависит от данных. Выбор так же трудится над уже отсортированным списком: чтобы убедиться, что первый элемент наименьший, надо посмотреть на все остальные, а помнить, что он узнал на прошлых проходах, выбор не умеет.

Зато обменов у выбора мало — не больше $n - 1$, по одному на позицию. Когда переставлять вещи гораздо дороже, чем сравнивать (скажем, двигать тяжёлые ящики на складе, сверяясь с накладными), это его козырь.

Раунд третий: вставки

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

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

На отсортированном списке — 999 сравнений, по одному на карту: каждая сразу видит, что стоит на месте. На развёрнутом — 499 500, то есть $\frac{n(n-1)}{2}$, как у выбора: каждая новая карта едет в самое начало. На перемешанном — около четверти миллиона, примерно $n^2/4$: в среднем карта проезжает половину руки. Лучший и худший случаи из главы 13 разошлись здесь на целый порядок роста: $\Theta(n)$ против $\Theta(n^2)$.

Что именно измеряет работа вставок? Назовём инверсией пару элементов, которые стоят не по порядку: больший слева, меньший справа. Каждый сдвиг в цикле while меняет местами одну такую пару, соседнюю, и больше ничего не трогает. Значит, сдвигов ровно столько, сколько в списке инверсий, а сравнений — не больше, чем инверсий плюс $n - 1$. В почти отсортированном списке, где лишь несколько карт стоят не на месте, инверсий мало, и вставки справляются почти за линейное время. Поэтому их и берут для коротких и почти готовых списков; короткие куски ими сортирует и встроенная сортировка Python.

Напрашивается улучшение. Левая часть руки отсортирована, значит, место для новой карты можно искать двоичным поиском (о нём — ниже): $\log_2 i$ сравнений вместо $i$. Сравнений станет порядка $n \log n$. Но место мало найти — туда надо вставить, а для этого сдвинуть вправо всё, что больше. В начале главы 17 мы вставляли так числа функцией bisect.insort и видели: вдвое больше чисел — вчетверо дольше. Квадрат никуда не делся, он переехал из сравнений в сдвиги.

Раунд четвёртый: пузырёк

Пузырёк вы видели в гонке из главы 0. Он идёт по списку и меняет местами соседей, стоящих не по порядку; за один проход самый большой элемент «всплывает» в конец, как пузырь в воде. Добавим одну заботу: если за целый проход не случилось ни одного обмена, список уже отсортирован и можно остановиться.

Пузырёк меняет местами только соседей, поэтому, как и вставки, исправляет инверсии по одной: обменов у него столько же, сколько сдвигов у вставок. Но сравнений у него обычно больше, а каждый обмен — две записи в список, тогда как сдвиг у вставок — одна. И у него есть странная асимметрия: большой элемент в начале списка доезжает до конца за один проход, а маленький в конце сдвигается влево лишь на одну позицию за проход. Список [2, 3, 4, 5, 6, 1] почти отсортирован, но пузырьку нужно пять проходов.

Дональд Кнут в третьем томе «Искусства программирования» вынес пузырьку приговор: «Короче говоря, у пузырька, похоже, нет никаких достоинств, кроме броского названия и того, что он ведёт к нескольким интересным теоретическим задачам». Приговор знают и за пределами профессии.

Турнирная таблица

Пора свести участников вместе. В таблице ниже все сортируют один и тот же список. Рядом с нашей тройкой выступают гость из главы 18, пирамидальная сортировка, и встроенная функция sorted. Сравнения и перестановки нашей четвёрки посчитаны прямо в браузере, сравнения sorted — заранее, в самом Python. А время каждый участник покажет на нашем сервере, по кнопке. Пройдитесь по видам данных и размерам.

У выбора число сравнений не меняется ни от чего. Вставки на почти отсортированных данных обходят всех, даже пирамидальную: сравнений чуть больше $n$. На перемешанных они делают вдвое меньше сравнений, чем выбор, а на развёрнутых — столько же. Пузырёк делает столько же перестановок, сколько вставки, но платит за каждую дороже и на перемешанных данных проигрывает по времени всем. Пирамидальная сортировка работает за $n \log n$ на любом входе, и на десяти тысячах элементов это уже другая лига. А sorted обгоняет всех: отчасти потому, что написана на языке C, но больше потому, что сравнений ей нужно в десятки и сотни раз меньше, чем квадратичным.

Последняя колонка таблицы — об ещё одном свойстве. В главе 10 мы заметили, что sorted не перемешивает записи с одинаковым ключом. Не все сортировки так умеют. Отсортируем по оценке список учеников, записанный по алфавиту.

После выбора Вера оказалась впереди Ани, хотя оценки у них равны, а по алфавиту Аня первая. Виноват первый же обмен: наименьшую оценку, тройку Гоши, выбор поставил на место Ани, а Аню отправил в конец, через голову Веры. Сортировку, которая сохраняет взаимный порядок равных элементов, называют устойчивой. На устойчивости держится приём из главы 10: отсортировать сначала по второстепенному ключу, потом по главному — и получить порядок по двум ключам сразу. С выбором этот приём не работает. Вставки и пузырёк устойчивы, пока двигают элемент только мимо строго большего соседа. Замените в них > на >= — список по-прежнему отсортируется, но равные начнут меняться местами.

Приз: двадцать вопросов

Порядок наводят прежде всего ради поиска. В неупорядоченном списке найти число можно только перебором: смотреть на элементы по очереди, пока не попадётся нужный. Это линейный поиск, так работает x in список, и в главе 13 мы видели, как его время растёт вместе с длиной списка. А в отсортированном списке можно играть в «двадцать вопросов» из главы 0: сравнить искомое с серединой и отбросить половину, в которой его заведомо нет. Это двоичный поиск. Миллион элементов — двадцать сравнений, миллиард — тридцать.

Описание укладывается в одно предложение, код — в десяток строк, и всё же этот код — одна из самых знаменитых ловушек программирования.

Бентли просил читателя отложить книгу и сначала попробовать самому. Попробуйте. В ячейке ниже — правдоподобная первая попытка и строгий судья. Судья перебирает сотни маленьких списков, с повторами и без, и ищет в них всё подряд: числа, которые есть, которых нет, меньше всех и больше всех. Запустите, найдите ошибку, исправьте и запустите снова.

Ошибка — в одной строке: lo = mid. Когда в отрезке остаётся один элемент, mid совпадает с lo, и если искомое больше a[mid], отрезок перестаёт сжиматься — цикл крутится вечно. Исправление — lo = mid + 1: элемент a[mid] уже проверен, ему в отрезке не место. Судья нашёл ошибку перебором. Но можно ли без гадания знать заранее, что каждая строка верна?

Инвариант

В двоичном поиске каждая строка выглядит очевидной, и ошибки прячутся в границах: < или <=, mid или mid + 1, len(a) или len(a) - 1. Чтобы не гадать, программисты формулируют инвариант цикла — утверждение, которое верно перед первой итерацией и остаётся верным после каждой. Для нашего поиска он такой: если x есть в списке, то он лежит в срезе a[lo:hi]. Срез полуоткрытый, как range: lo входит, hi — нет. Дальше остаётся проверить четыре вещи.

1. В начале инвариант верен. lo = 0, hi = len(a): срез — весь список.
2. Шаг его сохраняет. Если a[mid] < x, то в отсортированном списке левее mid и на самом mid тоже всё меньше x; значит, x может быть только в a[mid + 1:hi], и lo = mid + 1 ничего не теряет. Если a[mid] > x, то x может быть только в a[lo:mid], и верно hi = mid.
3. Выход даёт ответ. Цикл кончается, когда lo == hi: срез пуст, и по инварианту x в списке нет.
4. Цикл кончается. При lo < hi середина удовлетворяет lo <= mid < hi, поэтому и mid + 1, и mid строго уменьшают длину среза.

Ошибочная версия нарушала четвёртый пункт: lo = mid при mid == lo ничего не меняет. Остальные три она выполняла, поэтому и ответы, если цикл всё-таки кончался, были верными. Другие типичные ошибки собраны в машине ниже, и у каждой свой сломанный пункт.

Где начинаются нужные

В машине работает ближайший родственник двоичного поиска, и на практике он полезнее. Вопрос «есть ли x и где» задают реже, чем другой: где в отсортированном списке начинаются элементы, не меньшие x. Ответ на него — и место, куда вставить x, не нарушив порядка, и число элементов меньше x, и начало всех слов на «мир» в словаре. В C++ эта функция называется lower_bound, в Python — bisect_left. Инвариант у неё про обе части списка сразу.

Здесь нет ни одной проверки на равенство. Каждое сравнение делит список на «меньше x» и «не меньше x», а цикл двигает границу между ними, пока неизвестная середина не исчезнет. Повторы не мешают: для x = 8 ответ — первая из трёх восьмёрок. А обычный двоичный поиск получается из lower_bound одной строкой: найти границу и проверить, стоит ли на ней x. Итераций — не больше $\lceil \log_2 (n + 1) \rceil$: срез каждый раз хотя бы вдвое короче.

В Python это уже написано, в модуле bisect: bisect_left — наш lower_bound, bisect_right — первый элемент, строго больший x, insort — вставка с сохранением порядка, которой мы пользовались в главе 17. С версии 3.10 им, как и sorted, можно передать key. Вот поиск в словаре «Войны и мира» — всех разных слов романа, разложенных по алфавиту:

В словаре 51 787 слов, и каждый из двух поисков задал не больше шестнадцати вопросов: $2^{16} = 65\,536$. Граница «мис» — маленькая хитрость: после «р» в алфавите идёт «с», поэтому всё, что начинается на «мир», лежит перед «мис». Так же, двумя двоичными поисками, база данных отвечает на запрос «все записи от и до» — к этому мы вернёмся в главе 46.

Что не так со средним арифметическим? В Java тип int — 32 бита, наибольшее значение $2^{31} - 1 = 2\,147\,483\,647$. Если в массиве больше миллиарда элементов, сумма двух индексов может не поместиться, и случится переполнение, как в главе 11: сумма завернётся в отрицательное число, а «середина» окажется за пределами массива. Повторим это в numpy, где целые числа такие же, как в Java. Numpy хотя бы предупредит о переполнении, Java молчала.

Ошибка проявляется только на массивах от $2^{30}$ элементов, то есть от миллиарда. Когда писались «Жемчужины», таких массивов не было; к 2006 году, писал Блох, они стали обычным делом в Google и не только. Исправление — low + (high - low) / 2: разность двух индексов всегда помещается. В Python целые числа не переполняются, и эту ошибку на нём не повторить. Урок Блоха относится к любому языку: доказательство Бентли было верным, но опиралось на допущение, о котором никто не подумал, — что сумма двух индексов помещается в ячейку. «Мало доказать, что программа верна, — заключил Блох, — её нужно ещё и проверить тестами».

Судья: быстрее нельзя

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

Возьмём три карты: $a$, $b$ и $c$. Алгоритм начинает с какого-то сравнения, скажем «$a < b$?». От ответа зависит, что он спросит дальше, — получаются две ветки. В каждой — следующий вопрос и снова две ветки, и так, пока алгоритм не остановится и не выдаст порядок. Это дерево решений: во внутренних узлах — вопросы, в листьях — ответы. Каждый вход проходит по дереву свой путь от корня до листа, и число сравнений на этом входе — длина пути.

У вставок шесть листьев, по одному на каждый из $3! = 6$ порядков, и самый длинный путь — три вопроса. У выбора листьев восемь, и два из них перечёркнуты: выбор иногда спрашивает то, что следует из прежних ответов, и одна из веток никогда не пригождается. У пузырька с флажком листьев семь, и перечёркнут один — по той же причине. Обойтись в худшем случае меньше чем тремя вопросами не может ни один из них, и причина у всех одна.

Это то же рассуждение, что в «двадцати вопросах»: чтобы выбрать один из $N$ вариантов ответами «да» и «нет», нужно $\lceil \log_2 N \rceil$ вопросов (в «Царице наук» это мера информации). У сортировки вариантов $n!$. Для пяти карт $\lceil \log_2 120 \rceil = 7$: вот откуда в первом раунде взялось число семь. Как растёт $\log_2 n!$? Распишем факториал:

$$\log_2 n! = \log_2 1 + \log_2 2 + \ldots + \log_2 n.$$

Каждое слагаемое не больше $\log_2 n$, поэтому вся сумма не больше $n \log_2 n$. С другой стороны, последние $n/2$ слагаемых — от $\log_2 \frac{n}{2}$ до $\log_2 n$ — каждое не меньше $\log_2 \frac{n}{2}$, и одни они дают не меньше $\frac{n}{2} \log_2 \frac{n}{2}$. Обе оценки растут как $n \log n$, значит, $\log_2 n! = \Theta(n \log n)$. Точнее это число описывает формула Стирлинга: $\log_2 n! \approx n \log_2 n - 1{,}44\, n$. Сравним границу судьи с тем, что делает sorted; сравнения посчитаем, подсунув ей числа в обёртке, которая считает вызовы <. Специальный метод __lt__ — тот, что Python вызывает для a < b, как в главе 12.

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

Вернитесь к картам из первого раунда и переключите судью в режим «хитрец». Хитрый судья не загадывает числа заранее. На каждый вопрос он отвечает так, чтобы вычеркнуть как можно меньше порядков: из двух ответов выбирает тот, после которого порядков останется больше. Каждый вопрос в лучшем для вас случае делит остаток пополам, а судья не даёт и этого лучшего случая. Против него никакая стратегия не обойдётся меньше чем семью вопросами на пяти картах. Партия с хитрецом — та же теорема, только разыгранная в картах. Такого судью называют противником, и доказательства «через противника» встречаются в теории алгоритмов постоянно.

Тем же рассуждением получается граница для поиска. У lower_bound на списке из $n$ элементов $n + 1$ возможный ответ, от $0$ до $n$, — значит, нужно не меньше $\lceil \log_2 (n + 1) \rceil$ сравнений. Двоичный поиск столько и делает, и двадцать вопросов на миллион чисел улучшить нельзя.

Вне зачёта: не сравнивать

Судья доказал теорему о тех, кто сравнивает. Но соблюдать правило «узнавать о данных только сравнениями» никто не обязан. Пусть надо отсортировать баллы миллиона выпускников, целые числа от 0 до 100. Сравнивать незачем: заведём 101 счётчик, пройдём по списку и посчитаем, сколько раз встретился каждый балл, а потом выпишем по порядку: столько-то нулей, столько-то единиц и так далее. Это сортировка подсчётом, и её время — порядка $n + k$ шагов, где $k$ — число возможных значений.

Подсчёт, написанный на Python, обгоняет sorted, написанную на C. Почему здесь не действует граница судьи? Сравнение отвечает «да» или «нет» — даёт один бит сведений. А строка counts[s] += 1 сразу отправляет балл в одну из 101 ячейки: это ответ на вопрос со ста одним вариантом. Граница $n \log n$ — об игре, где разрешены только вопросы «да или нет»; подсчёт играет в другую игру.

Подсчёт хорош, когда значений мало. Десятизначные номера телефонов так не отсортируешь: счётчиков понадобилось бы десять миллиардов. Выручает приём, которым сортировали перфокарты задолго до компьютеров: раскладывать по одной цифре.

Почему начинать с последней цифры, а не с первой? Попробуйте сами на машине ниже — и сломайте её двумя способами.

Это поразрядная сортировка. Почему она работает, видно из инварианта: после $k$ проходов колода упорядочена по последним $k$ цифрам. Перед первым проходом это верно — по нулю цифр упорядочено всё. Пусть после $k$ проходов колода упорядочена по последним $k$ цифрам, и мы раскладываем её по $(k+1)$-й цифре с конца. Две карты с разными $(k+1)$-ми цифрами попадут в разные карманы и встанут в правильном порядке. Две карты с одинаковой $(k+1)$-й цифрой попадут в один карман — и вот здесь нужна устойчивость: внутри кармана они должны сохранить порядок, который им дали прошлые проходы. Соберите карман снизу вверх, и инвариант сломается. А если начать со старшей цифры, последний проход перемешает всё по младшей.

Число проходов равно числу цифр, каждый проход — $n$ раскладок и десять карманов. Основание не обязано быть десятичным: по основанию 256 цифра — это байт, а 32-битное число — четыре цифры. Так что у вопроса Шмидта есть хороший ответ: миллион 32-битных чисел сортируется за четыре прохода поразрядной сортировки по байтам — четыре миллиона раскладок и ни одного сравнения. Платить за это приходится требованием к ключам: они должны резаться на цифры, как числа, строки и даты. Отсортировать так учеников «по росту, а при равном росте по алфавиту» ещё можно, а вот объекты с произвольным правилом сравнения — уже нет.

Чемпион: Timsort

Турнир выиграла встроенная sorted. Её алгоритм называется Timsort, по имени автора. В 2002 году Тим Петерс, один из основных разработчиков Python, автор «Дзена Python», заменил им прежнюю сортировку списков: с версии 2.3 списки в Python сортирует Timsort. Через несколько лет Джошуа Блох, автор заметки о переполнении, перенёс его на Java: с седьмой версии Java им сортирует массивы объектов, им же сортирует и Android.

Петерс исходил из наблюдения: данные из жизни редко бывают случайными. Список заказов отсортирован по времени, к нему дописали десяток новых; таблицу выгрузили по одному полю, а сортируют по соседнему, почти совпадающему. В таких данных есть серии — куски, которые уже идут по возрастанию (или строго по убыванию — такие Timsort разворачивает). Timsort находит серии одним проходом. Короткие серии он удлиняет до 32–64 элементов вставками из третьего раунда, причём место для карты ищет двоичным поиском: на коротких кусках сдвиги дёшевы. А потом сливает серии попарно, как две колоды карт, следя, чтобы сливаемые куски были близки по длине. Слияние — тема следующей главы. Посчитаем сравнения на данных разной степени готовности.

На готовом и на развёрнутом списке — всего $n - 1$ сравнение: вся колода — одна серия. На почти готовом — чуть больше $n$, на случайном — около процента сверх границы. Противоречия с судьёй нет: граница говорит о худшем случае, а отсортированный список для Timsort — лучший. Он не тратит сравнений на то, что уже сделано. И он устойчив, поэтому приёмы с key из главы 10 с ним работают.

Задачи

Четыре задачи. Две — про поиск, где всё решают границы, и две — про сортировку. Встроенными sorted, .sort() и модулем bisect в них пользоваться нельзя — тесты это проверят.

Напишите функцию binary_search(a, x): a отсортирован по неубыванию, функция возвращает индекс, на котором стоит x (если x встречается несколько раз — любой из них), или -1, если x нет. Тесты проверяют все границы, о которых шла речь в главе, и ещё одно: «список» может оказаться очень длинным — например, последовательностью из $10^{18}$ чисел, которые вычисляются по индексу и нигде не хранятся. Функция должна найти ответ за несколько десятков обращений к a[i]. Ещё один тест — сто тысяч поисков в миллионе чисел за три секунды. Модуль bisect и метод .index здесь под запретом.

Возьмите lower_bound из главы: он находит первый индекс i, где a[i] >= x. Осталось проверить, что на этом месте действительно x.

Осторожно с концом: если все элементы меньше x, граница равна len(a), и обращение a[len(a)] упадёт. Сначала проверьте индекс, потом значение. И не пользуйтесь x in a — на $10^{18}$ элементах перебор не кончится никогда.

Порядок проверок в последнем if важен: and не станет вычислять a[lo], если lo < len(a) ложно. На последовательности из $10^{18}$ элементов цикл делает 60 итераций — $2^{60} \approx 1{,}15 \cdot 10^{18}$.

Метеостанция записала температуры за много лет, и список отсортирован. Напишите count_in_range(a, low, high) — сколько элементов отсортированного списка a лежат в отрезке от low до high включительно. Если low > high, ответ — ноль. Например, в списке [-3, 0, 2, 2, 5, 7, 7, 7, 10] от 1 до 7 лежат шесть чисел. Функцию вызывают 200 000 раз на списке из миллиона чисел, и на всё даётся четыре секунды, так что перебор не годится.

Ответ — разность двух границ: где начинаются элементы, не меньшие low, и где начинаются элементы, строго большие high.

Вторая граница — это upper_bound: первый индекс, где a[i] > x. Он отличается от lower_bound одним знаком в условии. Каким и почему — подскажет инвариант: «всё в a[:lo] не больше x, всё в a[hi:] больше x». Подвох — в повторах на самих концах отрезка.

Если вместо upper_bound(a, high) взять lower_bound(a, high), потеряются все элементы, равные high, — тесты с повторами на концах ловят именно это. В модуле bisect эти две функции называются bisect_left и bisect_right.

Напишите insertion_sort(a, key=None), которая сортирует список a на месте сортировкой вставками и ничего не возвращает. Если key задан, сравнивать нужно key(x), как в sorted. Сортировка должна быть устойчивой. А ещё тесты подсунут почти отсортированный список из двухсот тысяч элементов: вставки обязаны справиться с ним за секунду — в этом их сила.

Если key не задан, подойдёт ключ «само значение»: key = lambda x: x. Ключ новой карты посчитайте один раз, до внутреннего цикла.

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

На почти отсортированном списке внутренний цикл почти сразу останавливается, и вся работа — около $n$ сравнений плюс по одному сдвигу на инверсию. Выбор на тех же данных сделал бы двадцать миллиардов сравнений. Ключ соседа key(a[j]) здесь считается заново на каждом шаге; если ключ дорогой, его можно посчитать заранее для всех элементов — так и делает sorted.

Напишите radix_sort(a), которая возвращает новый список с неотрицательными целыми числами из a по возрастанию. Сравнивать элементы между собой нельзя — только раскладывать по карманам, как машина Холлерита, от младшей цифры к старшей. Числа бывают разной длины, от нуля до $10^{18}$. Сто тысяч чисел нужно отсортировать за четыре секунды.

Один проход: заведите десять пустых списков-карманов, положите каждое число в карман по его цифре (x // place) % 10, где place — 1, 10, 100…, и соберите карманы с нулевого по девятый.

Сколько проходов? Пока place не превысит наибольшее число: у самого длинного числа все цифры уже учтены, а у коротких старшие цифры — нули. Наибольшее число найдёт функция max: сортировкой она не считается. Не забудьте про пустой список.

Устойчивость здесь бесплатная: append кладёт числа в карман в том порядке, в каком они пришли, а сборка выкладывает карман от начала к концу. Время — число цифр наибольшего числа, умноженное на $n$. Для чисел до $10^{18}$ это девятнадцать проходов; по основанию 256 хватило бы восьми.

Куда дальше

Выбор, вставки и пузырёк понятны с первого взгляда, но все трое квадратичны: на перемешанных данных их работа растёт как $n^2$. Быстрый процессор и аккуратный код тут не помогут: двоичный поиск места при вставке лишь переносит квадрат из сравнений в сдвиги, а флажок у пузырька выручает только на почти готовых данных. На миллиарде чисел квадрат — это порядка $10^{18}$ сравнений (у выбора $n^2/2 = 5 \cdot 10^{17}$), годы работы. Пол, который нашёл судья, лежит гораздо ниже, на $n \log n$, и до него дотягиваются пирамидальная сортировка из главы 18 и чемпион Timsort. Но куча — хитрое устройство под одну задачу, а сердце Timsort, слияние, мы пока видели только мельком. Нужна общая идея, которая даёт $n \log n$ по построению и годится не только для сортировки. Её в следующей главе принесут два человека, оказавшиеся в Московском университете почти одновременно.