Insertion Sort

O Insertion Sort interage por uma lista de itens e cada um destes itens é inserido em uma lista de itens na posição correta.

Use o Insertion Sort apenas para conjuntos de dados pequenos e com baixa entropia.

Pseudocode 1: Insertion Sort

\\entrada conjunto A com n elementos
              \\saída conjunto A de n elementos ordenados 
              
              ordene(A)
                  for i=1 até n-1
                      inserte(A, i, A[i])
              
              inserte(A, posição, valor)
                  i = posição - 1
                  while (i >= 0 E A[i] > valor ) do
                      A[i+1] = A[i]
                      i=i-1

Fonte: o autor (2020)

Merge Sort

O algoritmo Merge Sort é uma aplicação do padrão de construção de algoritmos dividir & conquistar.

• Dividir: divida o conjunto de entrada em dois. Exceto que este conjunto for muito pequeno;
• Recorrência: recursivamente ordene os dois conjuntos de dados resultantes;
• Conquistar: una os dois conjuntos.

Dividir

Se o conjunto $A$ tem zero, ou um elemento, retornos o conjunto $A$ já que ele já está ordenado. Você não consegue ordenar conjuntos vazios ou unitários. Caso a cardinalidade do conjunto $A$ seja maior que $1$, dividimos este conjunto em dois, $A_1$ e $A_2$ com cardinalidade proxima da metade da cardinalidade de $A$.

Recursividade e Conquista

Recursivamente ordene os itens de $A_1 e $A_2.

Junte, merge, $A_1 e $A_2 em $A.

Figura 1: árvore binária do Merge Sort.

Fonte: (GOODRICH; TAMASSIA; MOUNT, 2011)

Pseudocódigo 2: Algoritmo Merge Sort

mergeSort(S)
                \\entrada conjunto A com n elementos
                \\saída conjunto A de n elementos ordenados 
                
                if A.size() > 1
                    (A1, A2) ← partition(A, n/2)
                
                mergeSort(A1)
                mergeSort(A2)
                
                S ← merge(S1, S2)

Fonte: o autor (2020)