Улучшения для сортировки слиянием (Merge sort) с учётом современных реалий
Думаю, неплохо бы сделать сортировку слиянием с такими улучшениями:
1. Меньшее количество необходимой дополнительной памяти. Стандартная сортировка слиянием требует O(N) дополнительной памяти, реально сделать O(sqrt(N)). Память нынче в дефиците и довольно дорогая.
2. Многопоточность. Современные компьютеры многоядерные, эти ядра не мешало бы загрузить вычислениями.
3. Многопутевое слияние (multi-way merge). Это снижает количество обращений к основной памяти (RAM). В многоядерных системах достаточно вычислительных мощностей, и пропускная способность памяти становится узким местом.
4. Адаптивность. Это, по-простому говоря, не сортировать массив, если он уже отсортирован. Как в TimSort.
5. Низкоуровневые оптимизации. Возможно, не сильно нужно. Вряд ли будет заметная прибавка скорости при использовании многопоточности на многоядерных системах, так как там производительность упирается в память. Но, возможно, снизит потребление электроэнергии, что тоже неплохо.
И всё это нужно совместить в одном алгоритме, что может быть непростой задачей.
Self-proclaimed merge sort expert; предсказатель
Пассажиры «Яндекс Go» смогут сэкономить на поездке в часы, когда такси заказывают особенно много людей. В такие моменты сервис предложит опцию «Позже»: машина приедет не сразу, зато поездка будет стоить меньше. Скидку даст «Яндекс Go» за свой счёт, она не уменьшит доход водителей.
