Edição didática em português. O código e suas saídas preservam o original.

Merge sort em C

Divida, ordene e intercale arrays com tempo de O(N log N).

Merge sort divide o intervalo ao meio até obter partes de um elemento. Ao retornar da recursão, intercala duas partes ordenadas escolhendo repetidamente o menor dos primeiros elementos pendentes.

A intercalação também deve copiar os elementos restantes de qualquer metade. Escolher primeiro o elemento da metade esquerda em caso de empate permite preservar a estabilidade da ordenação. O método usual exige O(N) de espaço auxiliar, além da pilha de recursão.

Verifique tamanhos ímpares, valores repetidos e limites do buffer temporário. O tempo é O(N log N) mesmo quando a entrada já está ordenada, salvo otimizações adicionais.

Código C

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

int merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    if (L == NULL || R == NULL) {
        free(L);
        free(R);
        return 0;
    }

    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, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
    return 1;
}

int mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        if (!mergeSort(arr, l, m) || !mergeSort(arr, m + 1, r)) return 0;
        return merge(arr, l, m, r);
    }
    return 1;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    if (!mergeSort(arr, 0, n - 1)) {
        fputs("Memory allocation failed.\n", stderr);
        return EXIT_FAILURE;
    }
    printf("MergeSorted Array:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Abrir no compilador

Saída esperada

MergeSorted Array:
3 9 10 27 38 43 82

Perguntas frequentes

Por que o código e a saída continuam em inglês?

Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.