Merge Sort

Merge sort adalah algoritma sorting divide-and-conquer yang memecah array menjadi dua bagian, mengurutkan masing-masing secara rekursif, lalu menggabungkan kedua bagian yang sudah terurut. Berbeda dengan bubble dan insertion sort yang O(n²), merge sort menjamin O(n log n) pada semua kasus — best, average, dan worst. Algoritma ini juga stabil, menjadi pilihan utama untuk std::stable_sort. Pada Chapter ini kita akan membedah mekanisme divide-and-conquer, mengimplementasikan merge sort top-down (rekursif) dan bottom-up (iteratif), serta menganalisis kompleksitasnya. Pada akhir chapter kita akan paham mengapa merge sort menjadi standar untuk sorting yang harus stabil.

Aturan: Divide, Conquer, Combine #

Merge sort mengikuti tiga langkah divide-and-conquer:

1. Divide — bagi array menjadi dua subarray sama panjang pada mid = (lo + hi) / 2.
2. Conquer — urutkan kedua subarray secara rekursif.
3. Combine — gabungkan dua subarray terurut menjadi satu array terurut.

Mekanisme Divide-and-Conquer #

Setiap subarray dipecah hingga berukuran 1 (sudah terurut by default), lalu digabungkan kembali level demi level. Total kedalaman pohon rekursi adalah ⌈log₂ n⌉.

Operasi Merge: Menggabungkan Dua Array Terurut #

Operasi kunci pada merge sort adalah merge: menggabungkan dua array terurut menjadi satu array terurut dalam waktu linear. Algoritma membandingkan elemen terkecil yang belum diambil dari kedua subarray, lalu memasukkan yang lebih kecil ke output.

Mekanisme Merge #

Kiri:  [27, 38, 43]    Kanan: [3, 9, 10, 82]
                                    ^--- 3 < 27 -> ambil 3
                                    ^--- 9 < 27 -> ambil 9
                                    ^--- 10 < 27 -> ambil 10
                                    ^--- 82 > 27 -> ambil 27
        ^--- 38 > 82 ? tidak, 82 > 38 -> ambil 38
        ^--- 43 < 82 -> ambil 43
                                    ^--- ambil sisa 82
Hasil: [3, 9, 10, 27, 38, 43, 82]

Bila v[i] <= v[j], ambil dari kiri (menjaga stabilitas). Setelah satu sisi habis, sisanya langsung disalin.

Kode: Merge Sort Top-Down (Rekursif) #

#include <iostream>
#include <vector>
#include <algorithm>

void merge(std::vector<int>& v, int lo, int mid, int hi, std::vector<int>& buf) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (v[i] <= v[j]) buf[k++] = v[i++];   // <= untuk stabilitas
        else               buf[k++] = v[j++];
    }
    while (i <= mid) buf[k++] = v[i++];
    while (j <= hi)  buf[k++] = v[j++];
    for (int t = lo; t <= hi; ++t) v[t] = buf[t];
}

void merge_sort_recursive(std::vector<int>& v, int lo, int hi, std::vector<int>& buf) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort_recursive(v, lo, mid, buf);
    merge_sort_recursive(v, mid + 1, hi, buf);
    merge(v, lo, mid, hi, buf);
}

void merge_sort(std::vector<int>& v) {
    if (v.size() < 2) return;
    std::vector<int> buf(v.size());
    merge_sort_recursive(v, 0, static_cast<int>(v.size()) - 1, buf);
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {38, 27, 43, 3, 9, 82, 10};
    merge_sort(a);
    std::cout << "Top-down: "; print(a);
    return 0;
}

Output yang Dihasilkan:

Top-down:  3 9 10 27 38 43 82

Bedah Kode Baris-per-Baris #

1. std::vector<int> buf(v.size()): alokasi buffer sekali di awal, digunakan ulang oleh semua pemanggilan rekursif. Menghindari alokasi berulang yang akan membuat kompleksitas O(n log n) menjadi O(n²) akibat overhead alokasi.
2. merge_sort_recursive(v, lo, hi, buf): fungsi rekursif dengan batas [lo, hi] inklusif.
3. if (lo >= hi) return;: base case — subarray berukuran 0 atau 1 sudah terurut.
4. int mid = lo + (hi - lo) / 2;: titik pembagian. Bentuk (lo + hi) / 2 berisiko overflow untuk lo + hi besar.
5. merge(v, lo, mid, hi, buf): gabungkan dua subarray terurut v[lo..mid] dan v[mid+1..hi].
6. if (v[i] <= v[j]) buf[k++] = v[i++];: ambil dari kiri bila v[i] <= v[j]. Operator <= (bukan <) krusial untuk stabilitas — elemen yang equal dari kiri (indeks lebih kecil) diambil lebih dulu.
7. while (i <= mid) buf[k++] = v[i++];: sisa subarray kiri langsung disalin.
8. for (int t = lo; t <= hi; ++t) v[t] = buf[t];: salin hasil dari buf kembali ke v.

Kompleksitas #

Analisis: Recurrence T(n) = 2T(n/2) + O(n) #

Setiap level pohon rekursi melakukan total O(n) kerja (semua merge pada level tersebut menjumlahkan n elemen). Kedalaman pohon adalah ⌈log₂ n⌉ — setiap level membagi array menjadi dua. Maka T(n) = O(n log n). Hasil ini juga dapat diturunkan dengan Master Theorem kasus 2.

Variasi: Bottom-Up (Iteratif) #

Versi bottom-up menghilangkan rekursi: mulai dari subarray berukuran 1 (sudah terurut), gabungkan pasangan demi pasangan menjadi ukuran 2, lalu 4, 8, dan seterusnya hingga seluruh array terurut.

Kode: Merge Sort Bottom-Up #

#include <iostream>
#include <vector>
#include <algorithm>

void merge(std::vector<int>& v, int lo, int mid, int hi, std::vector<int>& buf) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (v[i] <= v[j]) buf[k++] = v[i++];
        else               buf[k++] = v[j++];
    }
    while (i <= mid) buf[k++] = v[i++];
    while (j <= hi)  buf[k++] = v[j++];
    for (int t = lo; t <= hi; ++t) v[t] = buf[t];
}

void merge_sort_bottom_up(std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    if (n < 2) return;
    std::vector<int> buf(n);
    for (int width = 1; width < n; width *= 2) {
        for (int i = 0; i + width < n; i += 2 * width) {
            int mid = i + width - 1;
            int hi = std::min(i + 2 * width - 1, n - 1);
            merge(v, i, mid, hi, buf);
        }
    }
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {38, 27, 43, 3, 9, 82, 10};
    merge_sort_bottom_up(a);
    std::cout << "Bottom-up: "; print(a);
    return 0;
}

Output yang Dihasilkan:

Bottom-up:  3 9 10 27 38 43 82

Bedah Kode Baris-per-Baris #

1. for (int width = 1; width < n; width *= 2): loop luar untuk ukuran subarray. Mulai dari 1, lalu 2, 4, 8, …, hingga width ≥ n.
2. for (int i = 0; i + width < n; i += 2 * width): loop dalam untuk setiap pasangan subarray pada level width. Kondisi i + width < n memastikan ada subarray kanan untuk digabung.
3. int mid = i + width - 1;: indeks terakhir subarray kiri.
4. int hi = std::min(i + 2 * width - 1, n - 1);: indeks terakhir subarray kanan — bisa kurang dari i + 2*width - 1 bila array tidak habis dibagi 2.
5. Kompleksitas: sama dengan top-down — O(n log n) waktu, O(n) ruang, tanpa overhead call stack.

Stabilitas #

Merge sort stabil berkat operator <= pada operasi merge. Saat v[i] == v[j], elemen dari kiri (indeks lebih kecil) diambil lebih dulu, sehingga urutan relatif elemen equal tetap terjaga.

In-Place? #

Merge sort standar tidak in-place — membutuhkan O(n) memori tambahan untuk buffer. Walaupun terdapat varian in-place merge sort (misalnya dengan algoritma block merge), kompleksitas konstanta jauh lebih besar dan implementasinya kompleks. Untuk kebanyakan kasus, O(n) tambahan memori adalah harga yang dapat diterima untuk jaminan O(n log n).

Optimasi Praktis #

1. Insertion sort cutoff — untuk subarray berukuran kecil (< 16), gunakan insertion sort alih-alih rekursi merge sort. Konstanta kecil insertion sort mengalahkan overhead rekursi merge sort.
2. Deteksi sudah terurut — sebelum merge, cek v[mid] <= v[mid+1]. Bila ya, subarray sudah terurut; skip merge.
3. Alternating buffer — bila buf digunakan sebagai tempat penyimpanan dan v sebagai output bergantian, kita dapat menghindari salinan buf -> v di akhir merge.

Penerapan: std::stable_sort #

STL C++ menyediakan std::stable_sort yang biasanya diimplementasikan sebagai merge sort dengan fallback ke insertion sort untuk sub-array kecil. Berikut perbandingan dengan std::sort:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Item { int key; std::string tag; };

int main() {
    std::vector<Item> items = {
        {5, "Budi"}, {3, "Andi"}, {5, "Citra"}, {3, "Dewi"}, {5, "Eka"}
    };

    auto a = items;
    std::sort(a.begin(), a.end(),
        [](const Item& x, const Item& y){ return x.key < y.key; });
    std::cout << "std::sort (mungkin tidak stabil):\n";
    for (const auto& it : a) std::cout << "  key=" << it.key << " tag=" << it.tag << '\n';

    auto b = items;
    std::stable_sort(b.begin(), b.end(),
        [](const Item& x, const Item& y){ return x.key < y.key; });
    std::cout << "\nstd::stable_sort (stabil):\n";
    for (const auto& it : b) std::cout << "  key=" << it.key << " tag=" << it.tag << '\n';

    return 0;
}

Output yang Dihasilkan:

std::sort (mungkin tidak stabil):
  key=3 tag=Andi
  key=3 tag=Dewi
  key=5 tag=Budi
  key=5 tag=Citra
  key=5 tag=Eka

std::stable_sort (stabil):
  key=3 tag=Andi
  key=3 tag=Dewi
  key=5 tag=Budi
  key=5 tag=Citra
  key=5 tag=Eka

1. std::sort menggunakan introsort (quick + heap + insertion). Pada kasus ini output kebetulan sama, namun stabilitas tidak dijamin.
2. std::stable_sort menggunakan merge sort — urutan relatif elemen equal (Budi, Citra, Eka dengan key=5) dijaga persis seperti input.
3. Implikasi: untuk multi-key sorting (sort by key1, lalu sort by key2 yang stabil terhadap key1), gunakan std::stable_sort.

Ringkasan #

• Merge sort adalah algoritma divide-and-conquer yang memecah, mengurutkan, lalu menggabungkan.
• Kompleksitas terjamin O(n log n) pada semua kasus — best, average, worst.
• Stabil berkat operator <= pada merge.
• Tidak in-place — membutuhkan O(n) memori tambahan untuk buffer.
• Dua varian utama: top-down (rekursif) dan bottom-up (iteratif). Keduanya memiliki kompleksitas sama.
• Menjadi basis std::stable_sort di STL C++.

Pada chapter berikutnya kita akan membahas quick sort — algoritma divide-and-conquer yang in-place dan rata-rata lebih cepat daripada merge sort, namun memiliki worst case O(n²).