Por que o valor de corte para classificação por inserção para pequenas submatrizes na otimização do algoritmo de classificação rápida depende do sistema?

Tenho uma 2ª edição, de 1984. Na página 112, sob o título "Pequenos subarquivos", em uma discussão sobre Quicksort:

A segunda melhoria decorre da observação de que um programa recursivo tem a garantia de chamar a si mesmo para muitos subarquivos pequenos, então ele deve ser alterado para usar um método melhor quando subarquivos pequenos são encontrados. Uma maneira óbvia de fazer isso é alterar o teste no início da rotina recursiva de if r>l thenpara uma chamada na ordenação por inserção (modificada para aceitar parâmetros que definem o subarquivo a ser ordenado), isto é if r-l <= M then insertion(l,r). Aqui, M é algum parâmetro cujo valor exato depende da implementação. O valor escolhido para M não precisa ser o melhor possível: o algoritmo funciona quase da mesma forma para M no intervalo de cerca de 5 a cerca de 25. A redução no tempo de execução é da ordem de 20% para a maioria das aplicações.

Há alguns pontos aqui.

Você está certo: o desempenho de um algoritmo é medido com base no número de operações que ele executa, não na velocidade do processador.

Como expliquei na minha resposta a uma pergunta semelhante , o Quicksort é um algoritmo extremamente complicado quando comparado ao Insertion sort. Há uma sobrecarga considerável de contabilidade envolvida. Ou seja, há certos custos fixos com o Quicksort, independentemente de quão grande ou pequeno seja o subarray que você está classificando. À medida que o array fica menor, a porcentagem de tempo gasto em sobrecarga aumenta.

Insertion sort é um algoritmo de classificação muito simples. Há muito pouca sobrecarga de contabilidade. Insertion sort pode ser mais rápido que Quicksort para arrays pequenos porque Insertion sort na verdade executa menos operações que Quicksort quando os arrays são muito pequenos. A variação (como diz o texto, de 5 a 25) depende das implementações exatas do algoritmo.

O livro de Sedgewick, assim como muitos outros textos de algoritmos, frequentemente confunde a linha entre o teórico e o prático. Acho que é bom manter o prático em mente, mas ou o autor deve deixar claro quando estiver falando sobre desempenho real e desempenho teórico , ou o instrutor deve esclarecer isso em sala de aula.