Почему внезапное переключение на стратегию сверху вниз в std::list::sort()?

В Visual Studio 2015 (VS2015), Microsoft изменила стратегию сортировки std::list::sort() с традиционной снизу вверх. Сортировка слиянием по принципу «сверху вниз». Это изменение исключило использование внутреннего массива списков и приняло итераторы для отслеживания границ отсортированных запусков в исходном списке.

Причины изменения

Стефан Т. Лавейв , разработчик нисходящего подхода, указал на необходимость избегать распределения памяти и создания нестандартных распределителей. В VS2015 появились распределители, которые больше не были конструктивными и сохраняющими состояние по умолчанию, что создавало проблемы при использовании предыдущего восходящего подхода.

Реализация нисходящего подхода

Верхний В подходе -down используется рекурсивный алгоритм, который рекурсивно делит список пополам, пока не достигнет базовых случаев, когда списки пусты или содержат один элемент. Функция _Sort делит список на три сегмента: левый сегмент, правый сегмент и конечный итератор. Логика слияния выполняется с использованием std::list::splice для перемещения узлов внутри исходного списка, обеспечивая безопасность исключений.

Аспекты производительности

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