Questão 67183

Um professor de Algoritmos e Estruturas de Dados está ensinando sobre algoritmos de ordenação. Ele quer que seus alunos compreendam os trade-offs entre diferentes algoritmos, não apenas em termos de complexidade de tempo no pior caso ($O(n^2)$ vs $O(n \log n)$), mas também em termos de comportamento com dados 'quase ordenados' e o uso de memória (in-place vs not-in-place). Para isso, ele apresenta três algoritmos: **Insertion Sort**, **Merge Sort** e **Quick Sort**. Ele cita um trecho de 'Algorithms' de Robert Sedgewick e Kevin Wayne: "Não existe um único algoritmo de ordenação que seja o melhor para todas as situações. O Insertion Sort, embora $O(n^2)$ no pior caso, é muito rápido para pequenas entradas ou para entradas que já estão quase ordenadas (complexidade linear). O Merge Sort tem uma garantia de desempenho de $O(n \log n)$, mas requer memória extra proporcional a $N$ para funcionar. O Quick Sort tem um desempenho médio excelente de $O(n \log n)$ e opera in-place (não requer memória extra significativa), mas seu pior caso é $O(n^2)$, que pode ocorrer se os pivôs forem escolhidos de forma inadequada, especialmente com dados já ordenados." O professor então propõe um cenário: um sistema precisa ordenar uma lista de 1 milhão de transações que chegam de um outro sistema. Sabe-se que essas transações já chegam 'quase ordenadas' por data, com apenas alguns poucos elementos fora de ordem.

Qual algoritmo de ordenação seria uma escolha surpreendentemente eficiente para este cenário específico e por quê?