Qual é a forma mais eficiente de classificar um milhão de inteiros de 32 bits?

Depende do que você quer dizer com eficiente. Tempo de execução? uso de memória? tempo para o primeiro resultado (algoritmo online)? tempo do programador? Com que frequência fará isto? Você se importa com o tempo decorrido (relógio) ou tempo de CPU - isto é, se você usar todos os núcleos disponíveis, ou eles já estão fazendo outro trabalho útil?Você está comparando o tempo médio? pior caso? Depende do que você sabe sobre a distribuição (como Joe Zbiciak menciona). A maioria das respostas assume uma distribuição uniforme, que você não encontra com muita freqüência em aplicações reais. Qual é a probabilidade de que o input invoque o pior dos comportamentos?>li>li> Depende de onde os inteiros vêm - estão todos na RAM, estão vindo através de uma conexão de rede lenta, estão espalhados por um sistema distribuído?li>li> Depende de onde os inteiros estão indo - estão sendo solicitados um a um por um usuário humano? Vai realmente precisar de ordenar todos eles? Será que o resultado precisa ser distribuído?É um resultado aproximado suficientemente bom para os seus propósitos? Uma resposta quase correta em 1ms seria melhor do que uma resposta exata em 30ms?Quanta RAM está disponível para você por espaço de trabalho?Por que você está classificando-os em primeiro lugar?Que outros casos você precisará considerar no futuro? Qual é a probabilidade de o caso de uso mudar para inteiros de 64 bits, digamos? Qual é a probabilidade de você precisar portar o código para outros processadores ou arquiteturas? Esta pretende ser uma biblioteca de propósito geral, ou é dedicada a algum problema específico importante? Vai precisar de ordenar 100 milhões de inteiros? Será que alguma vez precisará de ordenar mais números do que tem espaço de endereços (não é provável hoje em dia, uma vez que a maioria das máquinas tem 64 bits... mas ainda existem algumas aplicações a correr em microcontroladores de 32 bits) ou RAM?

Por exemplo:

• Se a sua entrada estiver quase ordenada para começar, a ordenação de inserção pode ser a melhor solução, mesmo que seja O(n^2) em geral. E não precisa de armazenamento auxiliar.
• Se houver apenas 1000 valores distintos, então um algoritmo de contagem será melhor.
• Se seus inteiros estão vindo em série, um algoritmo de heap pode ser melhor. Se eles forem distribuídos, você pode querer um algoritmo distribuído (embora a sobrecarga para algo tão pequeno quanto 1m de elementos provavelmente não faça isso valer a pena).
• Se o tempo para o primeiro resultado for crítico, uma ordenação de seleção é sua melhor aposta.
• Se você estiver ordenando para facilitar a pesquisa, uma tabela de hash é normalmente melhor. If you’re sorting them to find the median, there are more efficient algorithms.

etc.

But… most of the time, for such a small problem, you can ignore all the subtleties and just call the system sort algorithm.