Merge Sort

Merge sort adalah algoritma sorting berbasis divide-and-conquer: kita pecah array menjadi dua bagian, sortir masing-masing secara rekursif, lalu gabungkan hasilnya. Kompleksitas waktu stabil O(n log n) pada semua kasus—best, average, dan worst. Kelemahannya: algoritma membutuhkan memori tambahan O(n) untuk buffer sementara. Pada chapter ini kita akan mengimplementasikan merge sort rekursif dengan alokasi buffer eksternal, lalu versi wrapper yang menangani kasus edge.

Strategi Divide-and-Conquer #

Algoritma merge sort bekerja dalam tiga langkah:

1. Divide: bagi array menjadi dua sub-array dengan ukuran kira-kira sama.
2. Conquer: sort masing-masing sub-array secara rekursif.
3. Combine: gabungkan dua sub-array terurut menjadi satu array terurut.

Langkah combine (merge) adalah inti algoritma. Bila kedua sub-array sudah terurut, kita dapat menggabungkan keduanya dalam O(n) dengan dua pointer yang berjalan dari kiri ke kanan. Karena setiap level rekursi melakukan O(n) kerja penggabungan dan ada O(log n) level, total kompleksitas adalah O(n log n).

Visualisasi Konsep #

Diagram berikut memperlihatkan pohon rekursi merge sort pada array [38, 27, 43, 3]: tahap divide memecah array menjadi sub-array tunggal, lalu tahap merge menggabungkan kembali secara terurut:

Pada diagram di atas, merge sort bekerja dalam dua fase. Fase divide (panah turun) memecah array berukuran n menjadi dua sub-array berukuran n/2 secara rekursif sampai setiap sub-array hanya berisi satu elemen—pada titik ini sub-array otomatis terurut. Fase merge (panah naik) menggabungkan pasangan sub-array terurut menjadi sub-array yang lebih besar dan juga terurut, dengan kompleksitas O(n) per level. Karena ada O(log n) level dari root ke leaf, total kerja penggabungan adalah O(n log n). Untuk n = 4 elemen dibutuhkan log2(4) = 2 level rekursi; untuk n = 1.000.000 dibutuhkan sekitar 20 level.

Implementasi Rekursif #

Kita akan menulis merge sort dengan buffer sementara dialokasikan sekali di luar fungsi rekursif. Ini menghindari alokasi berulang di setiap level rekursi yang dapat memperlambat eksekusi.

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

/* Merge dua sub-array terurut: a[kiri..mid-1] dan a[mid..kanan] */
static void merge(int *a, int *tmp, int kiri, int mid, int kanan) {
    int i = kiri, j = mid, k = kiri;
    while (i < mid && j <= kanan) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j <= kanan) tmp[k++] = a[j++];
    for (int t = kiri; t <= kanan; t++) a[t] = tmp[t];
}

/* Merge sort rekursif */
void merge_sort(int *a, int *tmp, int kiri, int kanan) {
    if (kiri >= kanan) return;
    int mid = kiri + (kanan - kiri) / 2;
    merge_sort(a, tmp, kiri, mid);
    merge_sort(a, tmp, mid + 1, kanan);
    merge(a, tmp, kiri, mid + 1, kanan);
}

static void cetak(const int *a, int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void) {
    int a[] = {38, 27, 43, 3, 9, 82, 10, 55, 1};
    int n = sizeof(a) / sizeof(a[0]);
    int *tmp = malloc(sizeof(int) * (size_t)n);

    printf("Sebelum: ");
    cetak(a, n);

    merge_sort(a, tmp, 0, n - 1);

    printf("Setelah: ");
    cetak(a, n);

    free(tmp);
    return 0;
}

Output yang Dihasilkan:

Sebelum: 38 27 43 3 9 82 10 55 1 
Setelah: 1 3 9 10 27 38 43 55 82 

Array terurut. Implementasi ini stabil karena saat menggabungkan kita pakai a[i] <= a[j]—bila elemen sama, elemen dari sub-array kiri diambil lebih dulu, sehingga urutan relatif tetap.

Mari kita telaah baris-baris kode di atas:

1. Baris 6-15 (merge): gabung dua sub-array terurut ke tmp, lalu salin balik ke a. Pointer i berjalan di sub-array kiri (kiri..mid-1), pointer j di sub-array kanan (mid..kanan). Pada setiap langkah, ambil elemen yang lebih kecil dan tulis ke tmp[k++].
2. Baris 8 (while (i < mid && j <= kanan)): loop utama selama kedua sub-array masih punya elemen. Kompleksitas: setiap elemen diproses sekali, jadi total O(kanan - kiri + 1).
3. Baris 12-13 (while (i < mid) tmp[k++] = a[i++];): bila sub-array kiri masih sisa, salin sisanya langsung. Sudah pasti terurut karena berasal dari sub-array terurut.
4. Baris 14 (while (j <= kanan) tmp[k++] = a[j++];): sama untuk sub-array kanan.
5. Baris 15 (for (int t = kiri; ...) a[t] = tmp[t];): salin balik hasil merge dari tmp ke a.
6. Baris 18-24 (merge_sort): fungsi rekursif. Base case kiri >= kanan (sub-array dengan 0 atau 1 elemen) langsung return. Case rekursif: bagi di mid, sort kiri dan kanan, lalu merge.
7. Baris 32 (int *tmp = malloc(...)): alokasi buffer sekali di luar rekursi. Lebih efisien daripada malloc/free di setiap level rekursi.
8. Baris 41 (free(tmp);): bebaskan buffer setelah sort selesai.

Wrapper dengan Alokasi Internal #

Pemanggil merge sort tidak boleh dipaksa mengelola buffer sendiri. Kita dapat menulis wrapper yang mengalokasikan dan membebaskan buffer secara internal, sehingga API lebih bersih.

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

/* Wrapper merge sort dengan alokasi internal */
void merge_sort_internal(int *a, int *tmp, int kiri, int kanan) {
    if (kiri >= kanan) return;
    int mid = kiri + (kanan - kiri) / 2;
    merge_sort_internal(a, tmp, kiri, mid);
    merge_sort_internal(a, tmp, mid + 1, kanan);

    /* merge ke tmp lalu copy balik */
    int i = kiri, j = mid + 1, k = kiri;
    while (i <= mid && j <= kanan) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= kanan) tmp[k++] = a[j++];
    memcpy(a + kiri, tmp + kiri, sizeof(int) * (size_t)(kanan - kiri + 1));
}

void merge_sort(int *a, int n) {
    if (n < 2) return;
    int *tmp = malloc(sizeof(int) * (size_t)n);
    if (tmp == NULL) return;
    merge_sort_internal(a, tmp, 0, n - 1);
    free(tmp);
}

int main(void) {
    int a[] = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    int n = sizeof(a) / sizeof(a[0]);

    printf("Sebelum: ");
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");

    merge_sort(a, n);

    printf("Setelah: ");
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");

    /* Edge case: array kosong dan 1 elemen */
    int kosong[] = {0};
    merge_sort(kosong, 0);
    printf("Kosong OK\n");

    int satu[] = {42};
    merge_sort(satu, 1);
    printf("Satu elemen: %d\n", satu[0]);

    return 0;
}

Output yang Dihasilkan:

Sebelum: 5 2 8 1 9 3 7 4 6 
Setelah: 1 2 3 4 5 6 7 8 9 
Kosong OK
Satu elemen: 42

Wrapper merge_sort(int *a, int n) menyembunyikan kompleksitas buffer dari pemanggil. Pemanggil cukup memberi array dan ukuran—sama seperti qsort(). Penggunaan memcpy() (dari <string.h>) lebih cepat dari loop manual untuk menyalin blok memori karena GCC dapat mengoptimalkan ke instruksi SIMD.

Kompleksitas dan Karakteristik #

Tabel berikut merangkum karakteristik merge sort dibanding algoritma lain:

Keunggulan merge sort: kompleksitas worst case O(n log n) yang terjamin, stabil, dan cocok untuk mengurutkan linked list (tidak butuh akses acak). Kelemahan: butuh memori tambahan O(n), lebih lambat dari quicksort di average case karena konstanta lebih besar.