Memahami dan Menerapkan Merge Sort: Panduan Lengkap dengan Contoh Kode

Merge Sort adalah algoritma pengurutan yang efisien dan berbasis perbandingan. Dikenal karena performanya yang konsisten, terutama dalam skenario pengurutan data berukuran besar, Merge Sort beroperasi dengan prinsip “pecah dan kuasai”. Artikel ini akan membahas secara mendalam tentang Merge Sort, mulai dari konsep dasarnya, cara kerja, implementasi kode (dalam beberapa bahasa pemrograman), analisis kompleksitas waktu dan ruang, hingga perbandingan dengan algoritma pengurutan lainnya.

Daftar Isi

1. Apa itu Merge Sort?
2. Prinsip Kerja Merge Sort
3. Algoritma Merge Sort
4. Ilustrasi Visual Merge Sort
5. Contoh Kode Merge Sort
   1. Python
   2. Java
   3. C++
6. Analisis Kompleksitas
   1. Kompleksitas Waktu
   2. Kompleksitas Ruang
7. Kelebihan dan Kekurangan Merge Sort
8. Perbandingan dengan Algoritma Pengurutan Lain
   1. Merge Sort vs. Quick Sort
   2. Merge Sort vs. Heap Sort
   3. Merge Sort vs. Bubble Sort
9. Aplikasi Merge Sort
10. Kesimpulan

1. Apa itu Merge Sort?

Merge Sort adalah algoritma pengurutan yang menggunakan pendekatan divide and conquer. Pendekatan ini melibatkan pemecahan masalah besar menjadi sub-masalah yang lebih kecil dan lebih mudah dikelola, menyelesaikan sub-masalah ini secara rekursif, dan kemudian menggabungkan solusi dari sub-masalah ini untuk menghasilkan solusi untuk masalah asli.

Dalam konteks pengurutan, Merge Sort membagi array yang belum diurutkan menjadi dua bagian yang sama besar (atau hampir sama besar), mengurutkan setiap bagian secara rekursif, dan kemudian menggabungkan kedua bagian yang telah diurutkan menjadi satu array yang terurut. Proses penggabungan (merging) adalah inti dari algoritma ini.

2. Prinsip Kerja Merge Sort

Prinsip dasar Merge Sort dapat diuraikan dalam beberapa langkah:

1. Divide (Pecah): Jika array memiliki lebih dari satu elemen, bagi array menjadi dua bagian yang (kira-kira) sama besar.
2. Conquer (Kuasai): Urutkan setiap bagian secara rekursif dengan memanggil Merge Sort pada setiap bagian tersebut. Proses ini terus berlanjut hingga kita mendapatkan array dengan satu elemen saja (yang secara otomatis sudah terurut).
3. Merge (Gabung): Gabungkan dua bagian yang sudah terurut menjadi satu array yang terurut. Proses ini dilakukan dengan membandingkan elemen-elemen dari kedua bagian dan menempatkannya dalam array hasil penggabungan sesuai urutan yang benar.

3. Algoritma Merge Sort

Secara formal, algoritma Merge Sort dapat ditulis sebagai berikut:

1. MergeSort(array A, int left, int right)
   1. Jika left < right: (Artinya, jika array memiliki lebih dari satu elemen)
   2. mid = (left + right) / 2 (Hitung titik tengah array)
   3. MergeSort(A, left, mid) (Urutkan bagian kiri array secara rekursif)
   4. MergeSort(A, mid + 1, right) (Urutkan bagian kanan array secara rekursif)
   5. Merge(A, left, mid, right) (Gabungkan kedua bagian yang sudah terurut)
2. Merge(array A, int left, int mid, int right) (Prosedur penggabungan)
   1. n1 = mid – left + 1 (Ukuran bagian kiri)
   2. n2 = right – mid (Ukuran bagian kanan)
   3. Buat array sementara L[n1] dan R[n2] (Untuk menyimpan bagian kiri dan kanan)
   4. Salin A[left…mid] ke L[]
   5. Salin A[mid+1…right] ke R[]
   6. i = 0, j = 0, k = left (Inisialisasi indeks untuk L, R, dan A)
   7. Sementara i < n1 DAN j < n2:
      1. Jika L[i] <= R[j]:
      2. A[k] = L[i]
      3. i++
      4. Selain itu:
      5. A[k] = R[j]
      6. j++
      7. k++
   8. Sementara i < n1: (Salin sisa elemen dari L, jika ada)
      1. A[k] = L[i]
      2. i++
      3. k++
   9. Sementara j < n2: (Salin sisa elemen dari R, jika ada)
      1. A[k] = R[j]
      2. j++
      3. k++

4. Ilustrasi Visual Merge Sort

Untuk lebih memahami cara kerja Merge Sort, mari kita visualisasikan proses pengurutan array [8, 3, 1, 7, 0, 10, 2]:

1. Divide: Array awal [8, 3, 1, 7, 0, 10, 2] dibagi menjadi dua: [8, 3, 1, 7] dan [0, 10, 2].
2. Conquer: Setiap bagian dibagi lagi secara rekursif:
   • [8, 3, 1, 7] dibagi menjadi [8, 3] dan [1, 7].
   • [0, 10, 2] dibagi menjadi [0, 10] dan [2].
   • [8, 3] dibagi menjadi [8] dan [3].
   • [1, 7] dibagi menjadi [1] dan [7].
   • [0, 10] dibagi menjadi [0] dan [10].

   Pada titik ini, kita memiliki array dengan satu elemen, yang secara otomatis sudah terurut.

3. Merge: Proses penggabungan dimulai dari array dengan satu elemen:
   • [8] dan [3] digabung menjadi [3, 8].
   • [1] dan [7] digabung menjadi [1, 7].
   • [0] dan [10] digabung menjadi [0, 10].
   • [3, 8] dan [1, 7] digabung menjadi [1, 3, 7, 8].
   • [0, 10] dan [2] digabung menjadi [0, 2, 10].
   • [1, 3, 7, 8] dan [0, 2, 10] digabung menjadi [0, 1, 2, 3, 7, 8, 10].

Hasil akhirnya adalah array yang terurut: [0, 1, 2, 3, 7, 8, 10].

5. Contoh Kode Merge Sort

Berikut adalah contoh implementasi Merge Sort dalam beberapa bahasa pemrograman populer:

5.1. Python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Temukan titik tengah array
        left_half = arr[:mid] # Bagi array menjadi dua bagian
        right_half = arr[mid:]

        merge_sort(left_half) # Urutkan bagian kiri secara rekursif
        merge_sort(right_half) # Urutkan bagian kanan secara rekursif

        i = j = k = 0

        # Salin data ke array sementara L[] dan R[]
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Periksa jika ada elemen yang tersisa
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Contoh penggunaan:
arr = [8, 3, 1, 7, 0, 10, 2]
merge_sort(arr)
print("Array yang terurut adalah:", arr)

5.2. Java

public class MergeSort {

    void merge(int arr[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    void sort(int arr[], int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            sort(arr, left, mid);
            sort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void main(String args[]) {
        int arr[] = {8, 3, 1, 7, 0, 10, 2};

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println("Array yang terurut adalah:");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

5.3. C++

#include 
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {8, 3, 1, 7, 0, 10, 2};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, arr_size - 1);

    cout << "Array yang terurut adalah: \n";
    for (int i = 0; i < arr_size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

6. Analisis Kompleksitas

Memahami kompleksitas waktu dan ruang dari suatu algoritma sangat penting untuk mengevaluasi efisiensinya.

6.1. Kompleksitas Waktu

• Kasus Terbaik: O(n log n)
• Kasus Rata-rata: O(n log n)
• Kasus Terburuk: O(n log n)

Merge Sort memiliki kompleksitas waktu O(n log n) dalam semua kasus (terbaik, rata-rata, dan terburuk). Hal ini karena proses pembagian selalu membagi array menjadi dua bagian, yang membutuhkan log n langkah. Proses penggabungan membutuhkan waktu O(n), karena kita perlu membandingkan dan menggabungkan semua elemen dalam kedua bagian.

6.2. Kompleksitas Ruang

Kompleksitas ruang Merge Sort adalah O(n). Hal ini karena Merge Sort membutuhkan ruang tambahan untuk menyimpan array sementara selama proses penggabungan. Dalam implementasi tipikal, kita membutuhkan array sementara dengan ukuran total n.

7. Kelebihan dan Kekurangan Merge Sort

Kelebihan:

• Stabil: Merge Sort adalah algoritma pengurutan yang stabil, yang berarti bahwa elemen dengan nilai yang sama mempertahankan urutan relatifnya dalam array yang terurut.
• Performa yang konsisten: Memiliki kompleksitas waktu O(n log n) dalam semua kasus, sehingga memberikan performa yang dapat diprediksi.
• Cocok untuk data berukuran besar: Efektif untuk mengurutkan data berukuran besar.
• Dapat digunakan untuk pengurutan eksternal: Dapat diimplementasikan untuk mengurutkan data yang tidak muat di memori (misalnya, data yang disimpan dalam file).

Kekurangan:

• Membutuhkan ruang tambahan: Membutuhkan ruang tambahan O(n) untuk array sementara.
• Kurang efisien untuk data kecil: Untuk data berukuran kecil, algoritma pengurutan sederhana seperti Insertion Sort atau Selection Sort mungkin lebih efisien.
• Rekursif: Implementasi rekursif dapat menyebabkan stack overflow untuk array yang sangat besar (meskipun implementasi iteratif juga dimungkinkan).

8. Perbandingan dengan Algoritma Pengurutan Lain

Mari kita bandingkan Merge Sort dengan beberapa algoritma pengurutan populer lainnya:

8.1. Merge Sort vs. Quick Sort

• Kompleksitas Waktu:
  • Merge Sort: O(n log n) (semua kasus)
  • Quick Sort: O(n log n) (rata-rata), O(n^2) (terburuk)
• Kompleksitas Ruang:
  • Merge Sort: O(n)
  • Quick Sort: O(log n) (rata-rata), O(n) (terburuk) - in-place (dengan optimasi)
• Stabilitas:
  • Merge Sort: Stabil
  • Quick Sort: Tidak Stabil

Kesimpulan: Merge Sort memiliki performa yang lebih konsisten daripada Quick Sort, tetapi Quick Sort memiliki kompleksitas ruang yang lebih rendah (jika diimplementasikan secara in-place). Pilihan antara keduanya tergantung pada kebutuhan spesifik aplikasi. Jika stabilitas penting, maka Merge Sort lebih baik. Jika ruang menjadi perhatian utama dan stabilitas tidak penting, Quick Sort bisa menjadi pilihan yang lebih baik.

8.2. Merge Sort vs. Heap Sort

• Kompleksitas Waktu:
  • Merge Sort: O(n log n) (semua kasus)
  • Heap Sort: O(n log n) (semua kasus)
• Kompleksitas Ruang:
  • Merge Sort: O(n)
  • Heap Sort: O(1) - in-place
• Stabilitas:
  • Merge Sort: Stabil
  • Heap Sort: Tidak Stabil

Kesimpulan: Heap Sort memiliki keuntungan karena merupakan algoritma in-place (tidak membutuhkan ruang tambahan). Namun, Merge Sort lebih stabil. Dalam praktiknya, Heap Sort seringkali sedikit lebih lambat dari Merge Sort.

8.3. Merge Sort vs. Bubble Sort

• Kompleksitas Waktu:
  • Merge Sort: O(n log n) (semua kasus)
  • Bubble Sort: O(n^2) (terbaik, rata-rata, terburuk)
• Kompleksitas Ruang:
  • Merge Sort: O(n)
  • Bubble Sort: O(1) - in-place
• Stabilitas:
  • Merge Sort: Stabil
  • Bubble Sort: Stabil

Kesimpulan: Merge Sort jauh lebih efisien daripada Bubble Sort, terutama untuk array berukuran besar. Bubble Sort hanya cocok untuk array yang hampir terurut atau untuk tujuan pendidikan karena kesederhanaannya.

9. Aplikasi Merge Sort

Merge Sort digunakan dalam berbagai aplikasi, termasuk:

• Pengurutan eksternal: Mengurutkan data yang terlalu besar untuk dimuat ke dalam memori.
• Implementasi dalam perpustakaan pengurutan: Beberapa perpustakaan pengurutan standar menggunakan Merge Sort atau variannya.
• Pengolahan data: Digunakan sebagai langkah dalam algoritma pengolahan data yang lebih kompleks.
• Perbandingan genom: Digunakan untuk mengurutkan dan membandingkan urutan DNA.

10. Kesimpulan

Merge Sort adalah algoritma pengurutan yang kuat dan serbaguna dengan kompleksitas waktu O(n log n) yang konsisten. Meskipun membutuhkan ruang tambahan, keuntungannya dalam stabilitas dan performa yang dapat diprediksi menjadikannya pilihan yang baik untuk berbagai aplikasi, terutama saat mengurutkan data berukuran besar. Dengan memahami prinsip kerja, implementasi kode, dan analisis kompleksitasnya, Anda dapat memanfaatkan Merge Sort secara efektif dalam proyek pengembangan perangkat lunak Anda.