Algoritmo Merge Sort – Implementação em Java, C e Python

O Merge Sort é um dos algoritmos de ordenação mais eficientes. Ele funciona com base no princípio de Dividir para Conquistar, baseado na ideia de dividir uma lista em várias sub-listas até que cada sub-lista consista em um único elemento e, então, mesclar essas sub-listas de maneira que resulte em uma lista ordenada.

Regra de Funcionamento do Merge Sort

O conceito de Dividir para Conquistar envolve três passos:

1. Dividir o problema em múltiplos subproblemas.
2. Resolver os Subproblemas. A ideia é quebrar o problema em subproblemas atômicos, onde eles são de fato resolvidos.
3. Combinar as soluções dos subproblemas para encontrar a solução do problema atual.

Portanto, a regra de funcionamento do Merge Sort envolve os seguintes passos:

1. Dividir o array não ordenado em subarrays, cada um contendo um único elemento.
2. Pegar pares adjacentes de arrays de um único elemento e mesclá-los para formar um array de 2 elementos.
3. Repetir o processo até que um único array ordenado seja obtido.

Um array de Tamanho ‘N’ é dividido em duas partes, ‘N/2’ tamanho de cada. Então, esses arrays são divididos ainda mais até chegarmos a um único elemento. O caso base aqui é alcançar um único elemento. Quando o caso base é atingido, começamos a mesclar a parte esquerda e a parte direita e obtemos um array ordenado no final. O Merge Sort quebra repetidamente um array em vários subarrays até que cada subarray consista em um único elemento e mesclando esses subarrays de maneira que resulte em um array ordenado.

Implementações do Merge Sort

Vamos implementar o algoritmo de ordenação Merge Sort em Java, C e Python.

Implementação em Java

public class MergeSort {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        int i = 0, j = 0;

        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            sort(arr, l, m);
            sort(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }

    public static void main(String args[]) {
        int arr[] = { 12, 11, 13, 5, 6, 7 };

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println("Sorted array");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

Output:

Sorted array
5 6 7 11 12 13

Este código define uma classe MergeSort em Java que implementa o algoritmo de ordenação por mesclagem (Merge Sort). O Merge Sort é um algoritmo de ordenação eficiente baseado no princípio de dividir para conquistar. Aqui está o que cada parte do código faz:

• Método merge: Este método é responsável por mesclar dois subarrays do array principal arr[]. Os parâmetros l, m, e r representam, respectivamente, o índice inicial, o ponto médio e o índice final do subarray que precisa ser mesclado. O método cria dois arrays temporários L[] e R[] para armazenar os elementos dos subarrays esquerdo e direito, copia os dados para esses arrays temporários e, em seguida, mescla os arrays temporários de volta no array original arr[] de maneira ordenada.
• Método sort: Este método é a implementação recursiva do Merge Sort, que divide o array em subarrays (esquerda e direita) até que cada subarray contenha apenas um elemento (divisão) e, em seguida, começa a mesclar esses subarrays de volta de forma ordenada (conquista). Ele faz isso encontrando o ponto médio m do subarray definido pelos índices l (esquerda) e r (direita), e chamando a si mesmo recursivamente para ordenar as duas metades do array antes de chamar o método merge para mesclar as metades ordenadas.
• Método main: Este método é o ponto de entrada do programa. Ele cria um array de inteiros arr[] com alguns valores não ordenados, cria uma instância da classe MergeSort, chama o método sort para ordenar o array inteiro (do índice 0 ao último índice) e, finalmente, imprime o array ordenado na saída padrão.

Em resumo, este código ordena um array de inteiros usando o algoritmo Merge Sort e imprime o array ordenado na saída padrão. É um exemplo clássico de aplicação do princípio de dividir para conquistar para ordenação de dados.

Implementação em C

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l+(r-l)/2;

        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    mergeSort(arr, 0, arr_size - 1);

    printf("Sorted array is \n");
    for (int i=0; i < arr_size; i++)
        printf("%d ", arr[i]);
    return 0;
}

Output:

Sorted array is 
5 6 7 11 12 13 

Este código é uma implementação do algoritmo de ordenação Merge Sort em C. Ele ordena um array de inteiros em ordem crescente. O código é dividido em três partes principais: a função merge, a função mergeSort e a função main. Aqui está o que cada parte faz:

Função merge

• Mescla dois subarrays de arr[].
• O primeiro subarray é arr[l..m] e o segundo subarray é arr[m+1..r].
• l, m, e r são índices do array, onde l é o índice do início do subarray, m é o meio, e r é o fim.
• Cria dois arrays temporários L[] e R[] para manter cópias dos subarrays que serão mesclados.
• Copia os dados para os arrays temporários e depois mescla os arrays temporários de volta no array arr[l..r] de forma ordenada.

Função mergeSort

• Ordena um subarray arr[l..r] usando o algoritmo Merge Sort.
• Se l < r (o subarray tem mais de um elemento), encontra o ponto médio m.
• Chama-se recursivamente para ordenar as duas metades: arr[l..m] e arr[m+1..r].
• Após ordenar as metades, utiliza a função merge para mesclar as duas metades ordenadas.

Função main

• Define um array arr com valores não ordenados.
• Calcula o tamanho do array arr_size.
• Chama a função mergeSort para ordenar o array inteiro arr[0..arr_size-1].
• Imprime o array ordenado.

Em resumo, este código demonstra como aplicar o algoritmo Merge Sort para ordenar um array de inteiros em C. O algoritmo Divide e Conquista é exemplificado aqui pela divisão do problema de ordenação em problemas menores (ordenando subarrays menores) e pela combinação de suas soluções (mesclando subarrays ordenados) para resolver o problema maior (ordenar o array inteiro).

Implementação em Python

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2  # Encontra o ponto médio do array
        L = arr[:mid]  # Dividindo a parte esquerda
        R = arr[mid:]  # Dividindo a parte direita

        mergeSort(L)  # Ordenando a primeira metade
        mergeSort(R)  # Ordenando a segunda metade

        i = j = k = 0

        # Mescla os arrays temporários de volta para arr[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Verifica se algum elemento foi deixado
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# Teste da função
arr = [12, 11, 13, 5, 6, 7]
mergeSort(arr)
print("Sorted array is:", arr)

Este código define uma função mergeSort que ordena um array (arr) em ordem crescente usando o algoritmo Merge Sort. O algoritmo divide o array em dois subarrays, ordena esses subarrays (recursivamente) e, em seguida, mescla os subarrays ordenados.

1. Divisão do Array: Divide o array dado pela metade até que subarrays de um único elemento sejam alcançados.
2. Ordenação e Mesclagem: Ordena e mescla esses subarrays para formar um array ordenado, comparando os elementos dos subarrays e os colocando na posição correta no array original.

Ao final, quando você executa a função mergeSort com o array de exemplo e imprime o array ordenado, o output será:

Sorted array is: [5, 6, 7, 11, 12, 13]

Complexidade de Tempo e Espaço do Merge Sort

1. Complexidade de Espaço
   Espaço Auxiliar: O(n) Ordenação In Loco: Não Algoritmo: Dividir para Conquistar
2. Complexidade de Tempo
   O Merge Sort é um algoritmo recursivo e sua complexidade de tempo pode ser expressa pela seguinte relação de recorrência: T(n) = 2T(n/2) + O(n). A solução da recorrência acima é O(nLogn). A lista de tamanho N é dividida em no máximo Logn partes, e a mesclagem de todas as sub-listas em uma única lista leva O(N) de tempo, portanto, o tempo de execução no pior caso deste algoritmo é O(nLogn).

• Complexidade de Tempo no Melhor Caso: O(n*log n)
• Complexidade de Tempo no Pior Caso: O(n*log n)
• Complexidade de Tempo Médio: O(n*log n)

A complexidade de tempo do MergeSort é O(n*Log n) nos 3 casos (pior, médio e melhor), pois o mergesort sempre divide o array em duas metades e leva um tempo linear para mesclar duas metades.

Resumo

Até agora, discutimos vários aspectos do algoritmo de ordenação Merge Sort, incluindo implementações em diferentes linguagens de programação, sua complexidade de tempo e espaço, e oferecemos uma análise sobre a eficácia do algoritmo. Aqui está um resumo dos pontos principais:

Implementações do Merge Sort

• Java, C, e Python: Fornecemos implementações do algoritmo Merge Sort nessas três linguagens de programação, destacando a abordagem de dividir para conquistar que caracteriza o algoritmo. Cada implementação segue a estrutura básica de dividir o array em subarrays até que cada um contenha um único elemento, e então mesclar esses subarrays de volta de forma ordenada.

Complexidade de Tempo e Espaço

• Espaço Auxiliar O(n): O Merge Sort requer espaço adicional proporcional ao tamanho do array para armazenar elementos temporariamente durante a mesclagem, o que resulta em uma complexidade de espaço O(n).
• Não é uma Ordenação In Loco: O algoritmo não ordena os elementos diretamente no array original sem usar espaço extra significativo.
• Complexidade de Tempo O(nLogn): Independentemente do caso (melhor, médio, ou pior), a complexidade de tempo do Merge Sort é O(nLogn), o que é derivado da sua natureza recursiva de dividir o array pela metade em cada etapa e levar um tempo linear para mesclar as duas metades.

Análise

• A análise sobre o Merge Sort confirma sua eficiência e confiabilidade, especialmente para conjuntos de dados grandes, devido à sua consistente complexidade de tempo O(nLogn) em todos os casos. Sua abordagem de dividir para conquistar permite que ele lide eficientemente com grandes volumes de dados, tornando-o uma escolha popular para ordenação.

Conclusão

• O Merge Sort é um algoritmo fundamental em ciência da computação, conhecido por sua eficiência, confiabilidade e complexidade de tempo previsível. Apesar de requerer espaço extra, suas vantagens em termos de performance o tornam uma escolha valiosa para a ordenação de arrays em muitas aplicações práticas e teóricas.