Escolher uma ordenação se resume a algumas propriedades: complexidade de tempo, estabilidade, uso de memória in-place e a natureza dos dados. Nenhuma ordenação vence em toda parte.
Escolher uma ordenação se resume a algumas propriedades: complexidade de tempo, estabilidade, uso de memória in-place e a natureza dos dados. Nenhuma ordenação vence em toda parte.
| Algoritmo | Tempo médio | Pior caso | Estável | In-place |
|---|---|---|---|---|
| Insertion | O(n²) | O(n²) | Sim | Sim |
| Merge | O(n log n) | O(n log n) | Sim | Não |
| Quick | O(n log n) | O(n²) | Não | Sim |
| Heap | O(n log n) | O(n log n) | Não | Sim |
# Most languages ship a tuned hybrid; prefer it in production
sorted(data, key=lambda x: x.priority) # stable Timsort in Python
Não implemente sua própria ordenação a menos que tenha um motivo específico — as ordenações de biblioteca (Timsort, introsort) são híbridos testados em batalha.
Alinhar a ordenação aos dados e requisitos evita tanto tempo desperdiçado quanto bugs sutis (como perder estabilidade).
Entender os compromissos explica por que as bibliotecas padrão escolheram híbridos como Timsort e introsort.
Este julgamento comparativo — não memorizar um algoritmo — é o que a engenharia real e entrevistas recompensam.