А поскольку мы знаем, что сортировка с объединением характеризуется линейно-логарифмической зависимостью от времени – O(n log n), то, с учетом того факта, что соревнуются 64 команды, мы можем ожидать, что для проведения турнира потребуется всего около 6 раундов (192 игры), а не бесконечных 63 раунда (2016 игр), которые понадобились бы, чтобы сформировать турнир.
«Шесть раундов March Madness» – звучит прекрасно. Но погодите секунду: 192 игры? Ведь этот турнир Национальной ассоциации студенческого спорта длится всего 63 игры.
В реальности турнир March Madness не может служить полноценным примером сортировки слиянием, поскольку в его рамках не производится полное упорядочение всех 64 команд. Ведь для того, чтобы по-настоящему ранжировать все команды, организаторы должны были бы вспомнить о линейно-логарифмической зависимости и назначить ряд дополнительных игр, чтобы определить серебряного призера, затем еще – для определения бронзового призера и т. д. Но этого не происходит на турнире. Вместо этого, точно копируя подход теннисного турнира, на который жаловался Доджсон, March Madness использует формат поочередного выбывания, где проигравшая команда, выбывая из соревнований, выбывает и из дальнейшей сортировки. Преимущество такого подхода заключается в том, что он использует линейную зависимость от времени, поскольку каждая игра исключает ровно одну команду. Поэтому, чтобы осталась одна команда, на турнире должно быть сыграно только (n − 1) игр. Минусом является тот факт, что вы никогда не поймете, какое место занимает ваша команда в общей турнирной таблице, если только не займете первое место.
Как ни странно, в формате поочередного выбывания вообще нет необходимости организовывать какую-либо соревновательную структуру, поскольку любые 63 игры всегда смогут выявить единственного и непобедимого чемпиона. Вспомните, например, игру «Царь горы»: одна из команд вызывает на бой одного за другим своих соперников до тех пор, пока их самих кто-нибудь не свергнет. И совершенно не важно, в какой момент произойдет смена царя горы и кто именно будет побежден. Новый царь горы займет место на троне, и игра вновь продолжится до победного конца. Этот вариант имеет недостаток: в любом случае вам понадобится проведение 63 отдельных раундов, поскольку игры не могут идти параллельно. Кроме того, может оказаться так, что одна команда должна будет играть все 63 игры подряд, что достаточно утомительно.
Хотя Майкл Трик и родился позже Доджсона почти на целый век, возможно, никто в XXI веке не продвинулся столь же далеко в своих математических исследованиях в спорте. Мы уже встречались с Майклом в этой книге, но спустя десятилетия с момента незадачливого применения им правила 37 % к своей личной жизни многое изменилось: он стал не только мужем и профессором в области операционных исследований, но и одним из основных организаторов матчей для Главной лиги бейсбола, а также таких конференций Национальной ассоциации студенческого спорта, как Big Ten и АСС. Майкл широко использует в работе принципы информатики.