Ordenação por mesclagem

8.1 Definição de ordenação por mesclagem

Ordenação por mesclagem (Merge Sort) — é um algoritmo de ordenação eficiente, estável e baseado em comparação, que utiliza a abordagem "dividir e conquistar" para ordenar elementos. O algoritmo divide o array em duas metades, ordena recursivamente cada metade e depois mescla as metades ordenadas em um único array ordenado.

Princípio de funcionamento:

Divisão:

• Divida o array original ao meio para obter dois subarrays.
• Repita o processo para cada subarray até que cada subarray se torne um array de um único elemento (ou vazio).

Mesclagem:

• Mescle dois subarrays vizinhos em um único array ordenado.
• Repita o processo de mesclagem até obter um único array ordenado.

Complexidade de tempo e espaço da ordenação por mesclagem

Complexidade de tempo:

• No pior caso: O(n log n)
• No caso médio: O(n log n)
• No melhor caso: O(n log n)

Complexidade de espaço:

O(n) — memória adicional necessária para armazenar subarrays temporários.

8.2 Método de mesclagem descendente

A sequência original é dividida recursivamente em metades até obtermos subsequências de 1 elemento. A partir das subsequências obtidas formam-se pares ordenados pelo método de mesclagem, depois quartetos ordenados e assim por diante.

Considere a sequência:

Dividimos a sequência em 2 metades (recursivamente, até obtermos pares).

Cada subsequência é ordenada pelo método de mesclagem e obtemos a sequência completa pronta.

8.3 Implementação do algoritmo de ordenação por mesclagem

Aqui é onde a recursão se torna útil! Este é um algoritmo muito bom e rápido em comparação com os anteriores. Ele divide o array ao meio, ordena ambas as partes separadamente e então rapidamente une as partes ordenadas.

Sua implementação fica mais ou menos assim:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Encontramos o meio do array
        left_half = arr[:mid]  # Dividimos o array em dois subarrays
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Ordenamos recursivamente a metade esquerda
        merge_sort(right_half)  # Ordenamos recursivamente a metade direita
        
        i = j = k = 0
        
        # Mesclagem das metades ordenadas
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # Checando elementos restantes
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# Exemplo de uso:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Array ordenado:", sorted_arr)
# Saída: Array ordenado: [3, 9, 10, 27, 38, 43, 82]

O ponto chave logo no começo:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Encontramos o meio do array
        left_half = arr[:mid]  # Dividimos o array em dois subarrays
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Ordenamos recursivamente a metade esquerda
        merge_sort(right_half)  # Ordenamos recursivamente a metade direita

Aqui é o que acontece:

1. Encontramos o meio do array
2. Dividimos o array em 2 partes
3. Ordenamos cada parte separadamente

Essa abordagem acelera muito o algoritmo.