A comparação que muitos já devem ter visto

Heap Sort e Insertion Sort aparecem em muitos cursos básicos.

Um é eficiente, outro é simples. $O(nlog\,n)\; \text{vs}\; O(n²)$.

Beleza. Isso é o esperado.

Mas esse tipo de comparação costuma parar na teoria. Aqui a ideia foi empurrar um pouco além:

colocar os dois sob as mesmas condições e observar o que acontece de verdade

Como montei o experimento

Nada muito elaborado — mas com cuidado suficiente pra não enviesar o resultado:

• os dois algoritmos recebem exatamente os mesmos dados
• cada um roda isoladamente
• medição com clock_gettime usando CLOCK_MONOTONIC
• foco direto em tempo de execução

A intenção não foi fazer benchmark acadêmico, mas também não deixar solto.

Estruturas

Cada algoritmo roda na sua própria estrutura, bem direta:

• Heap Sort com heap em array
• Insertion Sort com array dinâmico

Isso evita interferência entre implementações e mantém a comparação limpa.

Ambiente de execução

Os testes foram executados no meu notebook:

• CPU: AMD Ryzen 7 5825U (8 cores / 16 threads)
• RAM: 7.2 GiB
• Sistema: Debian GNU/Linux 12 (Bookworm)
• Arquitetura: x86-64
• Armazenamento: SSD
• Compilador: GCC
• Flags: -O2 -Wall -Werror

Isso é importante, dado que o tempo de execução não é absoluto, dependendo diretamente da máquina em que você roda.

O que aparece quando se começa a escalar

Com entradas pequenas, os dois algoritmos convivem bem.

O Insertion Sort até se mantém competitivo — o que faz sentido, já que ele tem baixo overhead.

Mas conforme o tamanho cresce, a diferença deixa de ser sutil.

Ela começa a ficar estrutural.

Gráficos de comparação

• Gráfico 1

Heap Sort — crescimento do tempo de execução

O crescimento é consistente. Nada surpreendente — mas também nada fora de controle.

• Gráfico 2

Insertion Sort — crescimento acelerado do tempo

O crescimento começa aceitável, mas rapidamente perde controle. O comportamento quadrático aparece sem disfarce.

• Gráfico 3

Heap Sort vs Insertion Sort — diferença de crescimento

Colocados lado a lado, não é mais uma questão de “qual é melhor”.

É uma questão de qual continua sendo viável.

O ponto em que a teoria vira limite real

Teve um momento no experimento que deixou isso bem claro.

Ao tentar escalar para 50 milhões de elementos, o Insertion Sort simplesmente deixou de ser uma opção prática.

Não por detalhe de implementação, mas por natureza do algoritmo.

$(5 \times 10^7)^2 = 2.5 \times 10^{15}$, esse seria o número total de operações a serem realizadas.

Mesmo com operações rápidas, isso escala para tempos absurdos.

É aqui que $O(n²)$ deixa de ser só uma notação e vira uma barreira concreta.

O que ficou mais evidente

Algumas coisas que já eram conhecidas ficam bem mais claras após a medição:

• Heap Sort mantém crescimento controlado
• Insertion Sort degrada rápido com escala
• a diferença não é só teórica — é operacional
• viabilidade depende diretamente da complexidade

E talvez o mais importante:

existe um ponto onde o algoritmo deixa de ser “lento” e passa a ser simplesmente inviável

Fechamento

Esse projeto não tenta reinventar nada.

Ele só coloca dois algoritmos clássicos no mesmo cenário e observa o comportamento com dados reais.

E quando você faz isso, a diferença entre eles deixa de ser um detalhe acadêmico.

Vira uma decisão prática.

Código

Você pode encontrar o projeto completo aqui.