Quicksort
Escolha um elemento, jogue tudo que é menor para a esquerda e tudo que é maior para a direita, e repita nas duas metades.
Tony Hoare o concebeu em 1959, aos 25 anos, em Moscou, quando tentava ordenar palavras para um exercício de tradução automática. Publicou-o na Communications of the ACM em 1961. A complexidade média é O(n log n), mas o pior caso é O(n²), e ele ocorre justamente quando o pivô cai sempre numa das pontas — por exemplo, em entrada já ordenada com escolha ingênua de pivô.
Apesar desse pior caso, na prática costuma vencer o merge sort: ordena in-place, tem excelente localidade de cache e quase não aloca memória. As bibliotecas padrão modernas trazem o introsort — um quicksort que troca para heapsort quando a recursão fica suspeitosamente funda, e para insertion sort em trechos curtos. Uma nota de cautela: em 2015, pesquisadores provaram que a implementação do TimSort em Java tinha um bug real nas verificações de invariantes.