Все преимущество этого метода заключается в том, что в нем применяется и линейное, и квадратичное время, а именно линейно-логарифмическое время, которое обозначается формулой O(nlog n).
Каждое перекладывание карты удваивает количество отсортированных пачек. Таким образом, чтобы полностью отсортировать n карт, вам необходимо переложить карты количество раз, равное цифре 2, умноженной на себя столько раз, чтобы конечный результат был равен n. Другими словами, это логарифм n по основанию 2.
Вы можете одновременно сортировать до четырех карт в два действия, до восьми карт третьим действием и до шестнадцати с помощью четвертого перекладывания. Подход «дели и побеждай», лежащий в основе метода сортировки с объединением, вдохновил на создание ряда других линейно-логарифмических алгоритмов, которые начали динамично развиваться. Сказать, что линейно-логарифмические алгоритмы – это всего лишь усовершенствованная версия квадратичных, – значит недопустимо занизить их значимость. В случае сортировки количества элементов, которое мы имеем при переписи населения, это промежуток между двадцатью девятью действиями по перекладыванию карт и тремя сотнями миллионов таких действий. Неудивительно, что этот метод выбирают для решения крупномасштабных промышленных задач.
Сортировка с объединением применяется также и в решении задач бытового масштаба. Отчасти причина популярности этого метода лежит в том, что такие сортировки легко выполняются параллельно. Если в ваши планы все еще входит наведение порядка на полке, то решение задачи согласно методу сортировки с объединением будет таким: закажите пиццу и пригласите несколько друзей; затем поделите количество книг поровну между вашими друзьями, и пусть каждый отсортирует свою часть; после этого пусть друзья разобьются по парам и отсортируют книги вдвоем. Процесс необходимо продолжать до тех пор, пока у вас не сложится две стопки книг и вам останется только объединить их в одну и поставить на полку. Только постарайтесь избежать жирных пятен от пиццы на книгах.
За гранью сравнения: перехитрить алгоритм
В неприметной промзоне неподалеку от города Престон округа Вашингтон, спрятавшись за общим входом в многочисленные офисы, расположился цех чемпиона Национальной библиотеки 2011 и 2013 года по сортировке. Длинный сегментированный конвейер переносит 167 книг в минуту – 85 000 в день – в сканер штрихкодов, где они автоматически перенаправляются к своего рода створкам бомбового отсека, через которые книги выбрасываются в одну из 96 корзин.
Сортировочный центр Престона – один из крупнейших и наиболее эффективных объектов в мире в области книжной сортировки. Центром управляет Библиотечная система округа Кинг. Она соперничает с аналогично оснащенной Публичной библиотекой Нью-Йорка уже четыре года, на протяжении которых организации попеременно передают пальму первенства друг другу. «Библиотека округа Кинг в этом году обойдет нас? – спросил заместитель директора управления библиотеки Нью-Йорка по работе с книжным фондом Сальваторе Магаддино прежде, чем вступить в новую схватку в 2014 году. – Даже не думайте».