Quick Sort (Ordenação rápida): Um algoritmo recursivo que escolhe um "pivô", particiona a lista em dois grupos (menores e maiores que o pivô) e ordena cada grupo recursivamente. Pseudocódigo simplificado:

funcao quickSort(lista) {
        se tamanho(lista) <= 1 então
                retornar lista
        pivô = lista[0]
        menores = [elementos < pivô]
        maiores = [elementos >= pivô]
        retornar quickSort(menores) + [pivô] + quickSort(maiores)
}

Complexidade: Média é O(n log n) e o pior caso é O(n²) (se o pivô for mal escolhido).

Merge Sort (Ordenação por mistura): Divide a lista em duas metades, ordena cada uma recursivamente e depois as junta de forma ordenada. Pseudocódigo:

funcao mergeSort(lista) {
        se tamanho(lista) <= 1 então
                retornar lista
        meio = tamanho(lista) / 2
        esquerda = mergeSort(lista[0..meio])
        direita = mergeSort(lista[meio..fim])
        retornar intercalar(esquerda, direita)
}

Complexidade: O(n log n).

Questões

Exercite seu aprendizado!