Como escolher o algoritmo de ordenação certo para sua lista

Bubble sort, quicksort e TimSort são os três algoritmos de ordenação que explicam o comportamento do sort nativo das linguagens modernas, e nenhum deles responde sozinho qual você deve usar. O bubble sort roda em O(n²) no pior caso; o quicksort fica em O(n log n) no caso médio e O(n²) no pior; o TimSort é o híbrido estável que Java e Python adotaram por padrão. Este guia compara os três com números e fontes primárias.

Bubble sort, quicksort e TimSort em uma frase

Bubble sort, quicksort e TimSort resolvem o mesmo problema com custos diferentes: o bubble sort compara pares vizinhos em O(n²) no pior caso, o quicksort particiona em torno de um pivô e roda em O(n log n) no caso médio, e o TimSort é um híbrido estável derivado do merge sort e da insertion sort. Nenhum deles é universalmente melhor.

A tabela abaixo resume a diferença que mais importa na prática: o pior caso. É ele que define se o seu serviço aguenta uma lista adversária ou um ataque de dados ordenados ao contrário.

O que é a notação Big O e por que constantes somem

A notação Big O descreve como o número de operações cresce conforme a entrada aumenta, ignorando constantes multiplicativas como 1/2. Quando um algoritmo de ordenação por seleção verifica n, depois n−1, depois n−2 elementos, a média é (1/2)·n por passada, mas o Big O final continua sendo O(n²).

Uma constante vira irrelevante em escala. Se você compara 500 milhões × 500 milhões com 500 milhões × 250 milhões, a segunda expressão é metade da primeira, mas continua na mesma ordem de grandeza. O que muda o jogo é o expoente, não o fator.

O gráfico de crescimento de Algoritmos de ordenação da Wikipedia ilustra por que curvas como O(n log n) e O(n²) se separam rápido. Uma constante dividida por dois não altera a forma da curva.

Referência rápida: complexidade e estabilidade

A escolha entre bubble sort, quicksort e TimSort depende de três variáveis: tamanho da entrada, distribuição dos dados e necessidade de estabilidade. Um algoritmo estável preserva a ordem relativa de elementos com chaves iguais, algo essencial quando você ordena por um critério secundário.

O TimSort é estável; o quicksort clássico, não. Essa diferença é o motivo declarado pelo Java Documentation para usar TimSort na ordenação de objetos, e não o quicksort.

Algoritmo	Melhor caso	Caso médio	Pior caso	Estável
Bubble sort	O(n)	O(n²)	O(n²)	Sim
Quicksort	O(n log n)	O(n log n)	O(n²)	Não (in-place típico)
TimSort	O(n)	O(n log n)	O(n log n)	Sim
Ordenação por seleção	O(n²)	O(n²)	O(n²)	Não

Como funciona o quicksort

O quicksort escolhe um elemento da lista, chamado pivô, separa os demais em menores e maiores que esse pivô, e repete o processo recursivamente em cada sublista até chegar ao caso base. O caso base é uma lista vazia ou com um elemento, que já está ordenada por definição.

Três passos definem a rotina: escolha um pivô, particione os demais elementos em dois subarrays, e aplique o quicksort em cada subarray. Depois, basta concatenar o subarray menor, o pivô e o subarray maior.

O custo de O(n log n) no caso médio vem de duas partes. O particionamento percorre todos os n elementos uma vez por nível de recursão. A divisão ao meio gera aproximadamente log n níveis até o caso base. O produto é n × log n.

Uma variante usada pelo Java para tipos primitivos adota dois pivôs em vez de um. O Java Documentation lista as versões de Arrays.sort disponíveis para arrays primitivos.

Escolha do pivô: onde a teoria separa do desempenho

A escolha do pivô não decide se o quicksort funciona, decide quanto ele custa. Escolher sempre o primeiro elemento de uma lista já ordenada produz partições desequilibradas, cada chamada remove um único elemento e o algoritmo degenera para O(n²).

A média de um pivô aleatório leva a partições razoavelmente equilibradas e aproxima o tempo real do O(n log n) teórico. Escolher a mediana de três valores, como primeiro, meio e último, reduz a chance de partições degeneradas em entradas quase ordenadas.

O quicksort in-place clássico não é estável. Quando dois registros têm a mesma chave, a partição troca a posição relativa deles, o que quebra qualquer ordenação secundária construída sobre ele.

Java e Python não usam quicksort por padrão

Java e Python usam TimSort nas ordenações de objetos, não quicksort. O TimSort, criado por Tim Peters em 2002, combina merge sort e insertion sort e explora trechos já ordenados que aparecem naturalmente nos dados.

O Java aplica quicksort de dois pivôs apenas para arrays de tipos primitivos, como int, long, double, char, short e byte. A documentação registra o TimSort do Python como implementação do sorted() e do list.sort().

Linguagem	Método	Algoritmo
Java	Arrays.sort em primitivos	Quicksort de dois pivôs
Java	List.sort e Arrays.sort em objetos	TimSort
Python	sorted() e list.sort()	TimSort
JavaScript	Array.prototype.sort	Comparação via callback
NumPy	numpy.sort	Quicksort como padrão

A estabilidade é o critério declarado. O quicksort in-place é instável, o que o torna inadequado como padrão para coleções de objetos em que a ordem relativa precisa sobreviver à ordenação.

JavaScript exige uma função de comparação no Array.prototype.sort e não garante estabilidade em todos os mecanismos historicamente, embora a especificação atual exija estabilidade desde o ECMAScript 2019.

Bubble sort: quando o O(n) do melhor caso ajuda

O bubble sort compara pares adjacentes e troca a posição quando estão fora de ordem, repetindo passadas até a lista ficar ordenada. Uma variante otimizada interrompe o loop quando uma passada inteira não realiza nenhuma troca, o que dá O(n) para uma lista já ordenada.

Esse melhor caso é a única vantagem prática do bubble sort. Em listas quase ordenadas e pequenas, ele compete; em listas grandes e desordenadas, o O(n²) o torna inviável contra o TimSort ou o quicksort.

Para ordenar um milhão de itens no pior caso, o bubble sort executa cerca de 10¹² comparações. O TimSort, em O(n log n), fica na casa de 2 × 10⁷ operações para o mesmo volume, uma diferença de cinco ordens de magnitude.

O que o benchmark da live mostrou

A live de Fernanda Kipper, publicada em 24 de agosto de 2026, rodou bubble sort e quicksort em um array pequeno de números e obteve o mesmo resultado ordenado, com custos e caminhos diferentes. O teste em escala pequena não distingue os dois algoritmos, porque o tamanho da entrada domina menos que a constante de execução.

Isso reforça o critério da própria live: escolher algoritmo só importa de fato na casa das centenas de milhares ou milhões de elementos. Abaixo disso, a diferença desaparece no ruído do hardware e do runtime.

Os tempos de execução estimados por aquele material partiam da suposição ilustrativa de 10 operações por segundo. Computadores reais executam muito mais que isso, então os segundos citados não devem ser lidos como medição.

TimSort, o híbrido que virou padrão

O TimSort foi projetado para dados do mundo real, que raramente chegam completamente desordenados. Ele detecta sequências já ordenadas, chamadas runs, e faz o merge delas, gastando menos trabalho quando o array tem ordem parcial.

Por ser estável e manter O(n log n) no pior caso, virou o padrão de fato em Python desde a versão 2.3 e no Java a partir do Java 7. O artigo TimSort no Python Developer's Guide descreve a implementação de referência na biblioteca padrão do CPython.

O TimSort é um exemplo de que o sort nativo de uma linguagem é uma decisão de engenharia, e não a tradução direta do algoritmo que aparece no livro didático.

FAQ: bubble sort, quicksort e TimSort

• Qual é o pior caso do quicksort? O pior caso do quicksort é O(n²), e ele acontece quando o pivô escolhido é sempre o menor ou o maior elemento da partição. Com pivô aleatório ou mediana de três, a chance de cair nesse cenário em listas reais é pequena.

• Bubble sort ainda é usado em produção? Raramente em produção, porque o O(n²) torna o custo proibitivo em listas grandes. Ele permanece útil no ensino, para visualizar trocas e complexidade, e em casos muito pequenos ou quase ordenados.

• Por que Java usa TimSort e não quicksort? Porque o quicksort in-place não é estável, e coleções de objetos frequentemente precisam preservar a ordem relativa de chaves iguais. O TimSort entrega estabilidade e mantém O(n log n) no pior caso.

• O Array.prototype.sort do JavaScript usa qual algoritmo? A especificação não exige um algoritmo específico, mas exige estabilidade desde o ECMAScript 2019. Na prática, cada motor implementa o seu próprio sort, geralmente híbrido, e você fornece o callback de comparação.

• Quicksort sempre é mais rápido que bubble sort? No caso médio, sim, porque O(n log n) supera O(n²) assim que a entrada cresce. No pior caso, o quicksort também chega a O(n²) e pode empatar com o bubble sort em dados adversários.

• O que significa um algoritmo de ordenação ser estável? Ser estável significa que dois elementos com a mesma chave mantêm a ordem relativa que tinham antes da ordenação. Isso importa quando a lista já vem ordenada por um critério secundário.

• Ordenar um milhão de itens com bubble sort é viável? No pior caso, não, porque o número de comparações chega à casa de 10¹². Um algoritmo O(n log n) faz o mesmo trabalho com dezenas de milhões de comparações.

• O NumPy usa quicksort por padrão? O parâmetro kind de numpy.sort aceita quicksort, mergesort, heapsort e stable, e o padrão histórico é o quicksort. Para estabilidade garantida, você precisa escolher explicitamente outra opção.

• Qual algoritmo de ordenação devo estudar primeiro? Comece pelo bubble sort para entender trocas e O(n²), depois avance para quicksort e entenda partição e pivô. O TimSort faz mais sentido quando você já domina merge sort e insertion sort.

Da teoria à sua próxima escolha

Ordenar listas parece resolvido até você precisar decidir por que uma chamada nativa se comporta diferente em Java, Python ou JavaScript. Bubble sort, quicksort e TimSort mostram que a resposta depende de estabilidade, distribuição dos dados e tamanho da entrada, não de um ranking absoluto.

Para se aprofundar, o Comprehensive Guide to Sorting Algorithms reúne implementações e comparações atualizadas, e o Computerphile tem explicações visuais de bubble sort e notação Big O.

Se você produz conteúdo em vídeo e quer transformar esse conhecimento em texto, o Skala Blog faz esse caminho: você cola a URL de um vídeo do YouTube e recebe uma transcrição organizada para virar artigo.

Vale acompanhar também o CrazyStack, comunidade que reúne conteúdo técnico em português. E se você quer conhecer quem explica algoritmos de forma direta no YouTube, procure o Dev Doido do canal do youtube.

Source video