Nederlandse leereditie

Merge sort in C: sorteren door samenvoegen

Verdeel een array en voeg gesorteerde delen samen met een tijdelijke buffer.

Merge sort verdeelt het interval tot delen van één element. Bij terugkeer uit de aanroepen voegt het twee gesorteerde delen samen door telkens het kleinste eerste overgebleven element te kiezen.

Kopieer daarna de resterende elementen van beide helften. Links kiezen bij gelijke waarden behoudt de stabiliteit. De gebruikelijke versie gebruikt O(N) hulpgeheugen, naast de recursiestack.

Test oneven lengtes, duplicaten en buffergrenzen. Zonder verdere optimalisatie blijft de tijd O(N log N), ook bij al gesorteerde invoer.

Broncode

#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;
}

Openen in de compiler

Verwacht resultaat

MergeSorted Array:
3 9 10 27 38 43 82

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.