Por que a mudança repentina para a estratégia de cima para baixo em std::list::sort()?

No Visual Studio 2015 (VS2015), a Microsoft mudou a estratégia de classificação de std::list::sort() do tradicional Merge Sort de baixo para cima para uma abordagem de cima para baixo. Essa mudança eliminou o uso de uma matriz interna de listas e adotou iteradores para rastrear limites de execução classificados dentro da lista original.

Razões para a mudança

Stephan T. Lavavej , o desenvolvedor da abordagem top-down, citou a necessidade de evitar a alocação de memória e a construção de alocadores não padrão. O VS2015 introduziu alocadores que não eram mais construtíveis e com estado padrão, o que apresentava problemas ao usar a abordagem ascendente anterior. A abordagem -down utiliza um algoritmo recursivo que divide recursivamente a lista em metades até atingir casos base onde as listas estão vazias ou contêm um único elemento. A função _Sort particiona a lista em três segmentos: execução à esquerda, execução à direita e o iterador final. A lógica de mesclagem é executada usando std::list::splice para mover nós dentro da lista original, mantendo a segurança da exceção.

Considerações de desempenho

Enquanto a lógica de cima para baixo abordagem aborda as questões de alocação de memória, ela vem com uma penalidade de desempenho em comparação com o Merge Sort original de baixo para cima. Para listas grandes com nós dispersos, a abordagem top-down sofre com aumento de perdas de cache, resultando em tempos de execução mais lentos. Nesses casos, pode ser mais rápido mover a lista para uma matriz ou vetor, classificá-la e criar uma nova lista a partir da matriz ou vetor classificado.