Алгоритм был изменен снизу вверх, сверху вниз, сортировка слиянием в Visual Studio 2015. Автор изменений заявил, что это было сделано для обработки списка без распределителя по умолчанию, но это можно было легко обработать с помощью get_allocator ()(исправление будет включать в себя экземпляр get_allocator () для каждого из 26 элементов в массиве списков) при объявлении списка.
update - изменение ключа для версии Visual Studioбыл переход от использования массива списков к использованию итераторов, хранящихся в стеке, и слиянию с помощью сплайсинга с подходом сверху вниз.Итераторы избежали проблем с отсутствием распределителей по умолчанию.и объединение с помощью сплайсинга, который предотвращал потерю данных в списке, если сравнение или другая проблема вызвала исключение.Однако оказывается, что подход снизу вверх с использованием массива итераторов и с использованием, по существу, того же слияния с помощью логики сплайсинга был возможен, хотя до недавнего времени я не пытался реализовать сортировку слиянием снизу вверх с использованием итераторов.Обсуждение в первой ссылке ниже теперь включает в себя пример кода сортировки слиянием снизу вверх с использованием итераторов.
Автор заметил, что переключение сверху вниз означало падение производительности, но правильно указывал, что если производительность была проблемой, то вВ большинстве случаев перемещение списка в вектор, сортировка вектора, а затем создание списка из отсортированного вектора выполняется быстрее.Тем не менее, большинство функций STL достаточно оптимальны, поэтому аргументом некоторых из них было то, что более ранний подход снизу вверх мог быть исправлен для обработки списка распределителей по умолчанию.
Хотя автор не упомянул об этом, вобсуждение в ссылке ниже, также было отмечено, что реализация сверху вниз позволяет избежать потери данных, если пользовательская функция сравнения выдает исключение.Однако другие функции STL, такие как std :: stable_sort (), потеряют данные, если функция сравнения выдает исключение, и у меня сложилось впечатление, что исключения, созданные пользовательскими функциями, не являются приоритетом для VS STL и должны быть обнаружены при отладочных сборках.
`std :: list <> :: sort ()` - почему внезапный переход на нисходящую стратегию?
В вики-статье приведен пример как сверху вниз, так исортировка слиянием снизу вверх для связанных списков:
https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists
https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists