Origem

Criado em 2002 por Tim Peters para a implementação CPython.

Foi criado sobre a ideia de que os conjuntos no mundo real contém dados quase ordenados.

É o algoritmo híbrido entre o Insertion Sort e o Merge Sort padrão do Python e do Java.

Propriedades

No melhor caso: $O(n)$;

Na média: $O(n log n)$;

No pior caso: $O(n log n)$;

Está entre os melhores.

Conceito

Um algoritmo especial é usado para dividir o conjunto de entrada em subconjuntos.

Cada subconjunto é ordenado com o Insertion Sort mais simples possível.

Estes subconjuntos, já ordenados, são reunidos com o Merge Sort

Definições

N: representa o comprimento do conjunto de entrada.

Run: um subconjunto ordenado do conjunto de entrada.

minRun: tamanho mínimo do subconjunto

minRun

O minRun será calculado de acordo com o N segundo os seguintes princípios:

1. Não deve ser muito grande para que o Insertion Sort seja efetivo.
2. Não deve ser muito pequeno para que o número de merges não seja muito grande.
3. Deve ser tal que $N/2$ seja uma potência de $2$

O último princípio é devido ao fato que o Merge Sort é mais eficiente em conjuntos cujo comprimento seja uma potência de $2$.

Galopando

Uma pequena, porém substancial mudança é feita no Merge Sort

Em vez de comparar todos os elementos dos dois conjuntos, uma janela $J$ é determinada.

Considerando o subconjunto mais baixo, ou a esquerda, os $J$ primeiros itens são comparados apenas com o primeiro item do subconjunto mais alto, ou a direita.

Se estes itens forem menores são colocados na posição correta. E uma nova janela $J$ é comparada com o primeiro número do subconjunto a direita.

Documentação

A publicação original de Tim Peters está disponível aqui.

Observe que ele cita que, na prática, o Tim Sort é muito mais eficiente que os algoritmos utilizados até então pelo Python e pelo Perl.

Material de apoio

Você pode baixar o material de apoio clicando aqui

Obras Citadas

AHO, A. V. et al. Compiladores: princípios, técnicas e ferramentas. 2º. ed. Boston, MA, USA: Pearson Education Inc. , 2007.
CASS, S. The 2016 Top Programming Languages. IEEE Spectrum, 2016. Disponível em: . Acesso em: 22 Set. 2016.