Стандарт не требует определенного алгоритма, он только должен быть стабильным и выполнять сортировку, используя приблизительно N lg N сравнений. Это позволяет, например, сортировку слиянием или версию со связанным списком быстрой сортировки (вопреки распространенному мнению, быстрая сортировка не является обязательно нестабильной, даже если самая распространенная реализация для массивов) .
С этой оговоркой, краткий ответ заключается в том, что в большинстве современных стандартных библиотек std::sort реализован как интросортировка (интроспективная сортировка), которая в основном является быстрой сортировкой, которая отслеживает глубину рекурсии и переключается на Heapsort (обычно медленнее, но с гарантированной сложностью O (n log n)), если Quicksort использует слишком глубокую рекурсию. Интросорт был изобретен сравнительно недавно (конец 1990-х годов). В старых стандартных библиотеках обычно использовалась быстрая сортировка.
stable_sort существует, потому что для сортировки массивов-подобных контейнеров большинство самых быстрых алгоритмов сортировки нестабильны, поэтому стандарт включает в себя как std::sort (быстрый, но не обязательно стабильный), так и std::stable_sort (стабильный, но часто несколько медленный) .
Однако оба из них, как правило, ожидают итераторы с произвольным доступом и будут плохо работать (если вообще будут) с чем-то вроде связанного списка. Чтобы получить достойную производительность для связанных списков, стандарт включает list::sort. Однако для связанного списка такого компромисса на самом деле не существует - довольно просто реализовать сортировку слиянием, которая одновременно стабильна и (примерно) так же быстро, как и все остальное. Поэтому им просто требовалась одна sort функция-член, которая должна быть стабильной.