Você trabalha na biblioteca da faculdade.
Bem no meio de uma tarde tranquila,
de repente, chega um carregamento com 1.280 livros diferentes.
Os livros foram deixados numa linha reta,
mas estão todos fora da ordem,
e o sistema de seleção automática está quebrado.
Para piorar as coisas, as aulas começam amanhã,
o que significa que logo de manhã cedinho
vai aparecer um monte de estudantes procurando por esses livros.
Como você vai conseguir organizá-los a tempo?
Um jeito seria começar numa extremidade da linha, com os dois primeiros livros.
Se os dois primeiros livros estiverem na ordem, então deixe-os onde estão.
Caso contrário, troque-os entre si.
Depois, olhe o segundo e o terceiro livro,
repita o processo,
e continue até chegar ao final da linha.
A uma certa altura, você vai chegar ao livro que deveria ser o último.
Continue trocando-o de lugar com os livros subsequentes,
passando-o de livro em livro até chegar ao fim da linha, onde é o lugar dele.
A seguir, comece do início e repita todo o processo
para colocar do segundo ao penúltimo livro nos lugares certos,
e continue até que todos os livros estejam organizados.
Essa abordagem se chama "método da bolha".
É simples, porém lento.
Você teria de fazer 1.279 comparações na primeira rodada,
depois, 1.278, e assim por diante,
chegando a 818.560 comparações.
Se cada uma levar apenas um segundo, o processo todo levará mais de nove dias.
Uma segunda estratégia seria começar ordenando apenas os dois primeiros livros.
Depois, pegar o terceiro e comparar com o livro na segunda posição.
Se ele estiver na frente do segundo livro, então troque os dois,
depois compare-o com o livro na primeira posição,
e troque de novo, se necessário.
Agora que ordenou os primeiros três livros,
continue a adicionar um livro de cada vez ao subconjunto ordenado,
comparando e trocando o novo livro com o que estiver antes dele,
até estar corretamente colocado entre os livros ordenados até então.
Isso se chama "ordenação por inserção".
Diferente do método bolha, ele em geral não exige que se compare cada par.
Em média, espera-se ser necessário comparar cada livro somente
com a metade dos livros que vieram antes dele.
Nesse caso, o número total de comparações
seria de 409.280, o que levaria quase 5 dias.
Você ainda teria comparações demais a fazer.
Eis aqui uma ideia melhor.
Primeiro, pegue um livro qualquer.
Chame-o de "a divisória" e compare-o com todos os outros livros.
Depois, divida a linha,
colocando todos os livros que vêm antes da divisória à esquerda desta,
e todos aqueles que vêm depois dela, à sua direita.
Você acabou de economizar um tempão
ao não ter de comparar nenhum dos livros da esquerda
com nenhum dos livros da direita.
Bem, olhando agora apenas os livros da esquerda,
você pode, de novo, eleger um "livro divisória" qualquer
e separar os livros que vêm antes dele daqueles que vêm depois.
Continue a criar subdivisões assim
até ter um monte de subconjuntos,
que você ordenará rapidamente usando outra estratégia: ordenação por inserção.
Cada rodada de divisão dessa requer cerca de 1.280 comparações.
Se suas divisões forem bem equilibradas,
dividir os livros em 128 subconjuntos de 10 levaria cerca de 7 rodadas,
ou 8.960 segundos.
Ordenar esses subconjuntos adicionaria cerca de 22 segundos para cada um.
No final das contas, esse método, conhecido como Quicksort,
poderia ordenar livros em menos de três a quatro horas.
Mas tem um porém.
Se as divisões ficarem desproporcionais, não haverá nenhuma economia de tempo.
Felizmente, isso raramente acontece.
E essa é a razão por que o Quicksort é uma das estratégias mais eficientes
usadas por programadores hoje em dia.
Eles a usam para coisas como ordenar itens por preço numa loja on-line,
ou criar uma lista dos postos de gasolina perto de um determinado lugar,
de acordo com a distância.
No seu caso, você terminou o "quick sorting" com tempo de sobra.
E lá se vai mais um dia eletrizante na biblioteca.