Merge Sort

Merge Sort adalah salah satu teknik mengurutkan data dengan cara memisahkannya, mengurutkan, dan menyatukan kembali data yang sudah urut.

Kelebihan: Efektif untuk jumlah data yang sangat banyak
Kekurangan: Membutuhkan ruang memori yang besar

Kompleksitas: O(n.log n)

Animasi visualnya dapat dilihat di visualgo.net/sorting.html

Berikut implementasinya dalam bahasa C.

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

void MergeSort(int *arr, int len)
{   if(len < 2) return;

    int mid = len / 2, right_len = len - mid;

    int *left = (int*)malloc(mid * sizeof(int));
    int *right = (int*)malloc(right_len * sizeof(int));

    int i;
    for(i = 0; i < mid; i++) left[i] = arr[i];
    for(; i < len; i++) right[i - mid] = arr[i];

    MergeSort(left, mid);
    MergeSort(right, right_len);

    int a = 0, b = 0;
    i = 0;

    while(a < mid && b < right_len)
        if(left[a] < right[b]) arr[i++] = left[a++];
        else arr[i++] = right[b++];

    while(a < mid) arr[i++] = left[a++];
    while(b < right_len) arr[i++] = right[b++];

    free(left);
    free(right);
}

int main()
{   /* Input */
    int n;
    scanf("%d", &n);

    int arr[n], i;
    for(i = 0; i < n; i++) scanf("%d", &arr[i]);

    /* Process */
    MergeSort(arr, n);

    /* Output */
    for(i = 0; i < n; i++) printf("%d ", arr[i]);
}

Contoh Input:
6
9 8 7 6 5 4

Contoh Output:
4 5 6 7 8 9