Bubble Sort vs Merge Sort: O que 10.000 Comparações Revelam

A Diferença Entre O(n²) e O(n log n)

A notação Big-O descreve como o tempo de execução de um algoritmo cresce conforme o tamanho da entrada aumenta. Vamos decodificar o que significa cada um:

Bubble Sort: O(n²)

Bubble Sort funciona comparando pares vizinhos e trocando-os se estiverem fora de ordem. A cada passada pelo array, o maior elemento "borbulha" para o final.

Para ordenar n elementos, ele faz aproximadamente n²/2 comparações:

• 50 elementos: ~1.225 comparações
• 100 elementos: ~4.950 comparações
• 200 elementos: ~19.900 comparações

Note o padrão: dobrar o tamanho quadruplica as operações. É isso que O(n²) significa — crescimento quadrático.

Merge Sort: O(n log n)

Merge Sort usa a estratégia "dividir para conquistar": divide o array ao meio recursivamente até ter pedaços de 1 elemento, depois combina esses pedaços em ordem.

Para ordenar n elementos, ele faz aproximadamente n log₂(n) comparações:

• 50 elementos: ~282 comparações (log₂(50) ≈ 5.64)
• 100 elementos: ~664 comparações (log₂(100) ≈ 6.64)
• 200 elementos: ~1.528 comparações (log₂(200) ≈ 7.64)

Aqui, dobrar o tamanho apenas dobra as operações (com um pequeno acréscimo logarítmico). Muito mais eficiente!

Os Números Não Mentem: Dados Reais do Sorting Arena

Usando o Sorting Arena da Simulabz, rodamos experimentos reais com diferentes tamanhos de array. Aqui estão os resultados:

Perceba como a diferença não é constante — ela aumenta conforme o array cresce. Com 200 elementos, Bubble Sort faz 13 vezes mais operações que Merge Sort!

Segundo pesquisas em ciência da computação, em um computador moderno, Bubble Sort leva aproximadamente 2 segundos para ordenar 10.000 elementos, enquanto Merge Sort leva apenas 0,015 segundos — uma diferença de 133×.

Por Que a Diferença Visual é Tão Dramática?

Quando você roda ambos os algoritmos lado a lado no Sorting Arena, a diferença é chocante:

• Merge Sort termina em poucos segundos, com as barras se reorganizando de forma quase instantânea.
• Bubble Sort fica "preso", com as barras trocando de posição lentamente, uma por uma, em um processo visivelmente mais longo.

Isso acontece porque Merge Sort faz movimentos "estratégicos" — cada divisão e combinação organiza grandes pedaços do array de uma vez. Já Bubble Sort faz movimentos "locais" — troca apenas vizinhos, então elementos precisam percorrer o array inteiro para chegar à posição correta.

"A diferença entre O(n²) e O(n log n) não é apenas teórica. É a diferença entre um algoritmo que funciona em segundos e um que trava por minutos em dados reais." — Donald Knuth, The Art of Computer Programming

Experimento Prático: Veja Você Mesmo

Quer testemunhar essa diferença com seus próprios olhos? Siga este experimento:

1. Acesse o Sorting Arena
2. Configure o Tamanho do Array para 150
3. Selecione Ordem Inicial como Aleatório
4. Nos algoritmos, ative apenas Bubble Sort e Merge Sort
5. Clique em ▶ Iniciar

Observe:

• Merge Sort termina em 1º lugar, geralmente com menos de 2.500 operações
• Bubble Sort ainda está processando quando Merge Sort já parou
• O contador de operações de Bubble Sort sobe para ~22.000, enquanto Merge Sort fica em ~2.200

Agora, tente novamente com 200 elementos. A diferença será ainda mais dramática!

Quando Usar Cada Um?

Bubble Sort: Apenas para fins didáticos

Bubble Sort é excelente para aprender conceitos de ordenação, mas nunca deve ser usado em produção com dados reais. A única exceção:

• Arrays minúsculos (menos de 10 elementos)
• Arrays já quase ordenados (Bubble Sort detecta isso e para cedo, atingindo O(n) no melhor caso)

Merge Sort: Para dados reais

Use Merge Sort (ou algoritmos similares como Quick Sort, Heap Sort) quando:

• Você precisa de desempenho garantido O(n log n) em todos os casos
• Os dados são grandes (n > 50)
• Você precisa de estabilidade (manter ordem relativa de elementos iguais)

Na prática, linguagens modernas já usam algoritmos eficientes internamente:

• JavaScript: Array.sort() usa Timsort (híbrido de Merge + Insertion)
• Python: sorted() também usa Timsort
• Java: Arrays.sort() usa Dual-Pivot Quick Sort

Perguntas Frequentes