Qual é a ideia principal e as vantagens do algoritmo de ordenação por fusão?

O algoritmo de ordenação por fusão (Merge Sort) baseia-se no princípio de "dividir e conquistar". Divide recursivamente o array original em duas metades, ordena cada uma delas e depois funde as duas partes ordenadas em um array ordenado.

Vantagens:

• Estabilidade: mantém a ordem dos elementos iguais.
• Tempo de execução garantido O(n log n) no pior, médio e melhor caso.
• Adequado para ordenar grandes volumes de dados e ordenação externa.

Exemplo em Java:

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    // Lógica de fusão de dois subarrays ordenados
}