Implementasi Merge Sort Contoh Kode & Penjelasan Detail

Memahami dan Mengimplementasikan Merge Sort: Kode Contoh & Penjelasan Mendalam

Merge Sort adalah algoritma pengurutan yang efisien dan berbasis perbandingan (comparison-based sorting algorithm). Algoritma ini mengikuti paradigma “divide and conquer” (bagi dan taklukkan) untuk memecah masalah pengurutan besar menjadi sub-masalah yang lebih kecil yang lebih mudah dipecahkan. Kekuatan Merge Sort terletak pada kemampuannya untuk memberikan performa yang konsisten, menjadikannya pilihan populer dalam berbagai aplikasi. Mari kita telusuri bagaimana Merge Sort bekerja, lengkap dengan contoh kode dan penjelasan detail.

Prinsip Dasar Divide and Conquer dalam Merge Sort

Strategi utama Merge Sort adalah membagi array yang belum diurutkan secara rekursif menjadi sub-array yang lebih kecil, hingga setiap sub-array hanya berisi satu elemen (elemen tunggal secara otomatis dianggap terurut). Setelah itu, sub-array yang terurut digabungkan kembali (merged) secara bertahap untuk menghasilkan array yang sepenuhnya terurut.

Proses ini dapat diilustrasikan sebagai berikut:

1. Divide (Bagi): Bagi array input menjadi dua bagian yang sama besar. Jika panjang array ganjil, satu bagian mungkin memiliki satu elemen lebih banyak.
2. Conquer (Taklukkan): Secara rekursif urutkan kedua sub-array tersebut menggunakan Merge Sort.
3. Combine (Gabungkan): Gabungkan dua sub-array yang sudah terurut menjadi satu array terurut. Langkah penggabungan ini adalah inti dari algoritma Merge Sort.

Implementasi Merge Sort dalam Kode (Python)

Berikut adalah contoh implementasi Merge Sort menggunakan bahasa pemrograman Python:

def merge_sort(arr):
  """
  Mengurutkan array menggunakan algoritma Merge Sort.

  Args:
    arr: Array yang akan diurutkan.

  Returns:
    Array yang telah diurutkan.
  """

  if len(arr) <= 1:
    return arr  # Basis rekursi: array dengan 0 atau 1 elemen sudah terurut

  mid = len(arr) // 2  # Temukan titik tengah array
  left = arr[:mid]     # Bagi array menjadi sub-array kiri
  right = arr[mid:]    # Bagi array menjadi sub-array kanan

  left = merge_sort(left)   # Urutkan sub-array kiri secara rekursif
  right = merge_sort(right)  # Urutkan sub-array kanan secara rekursif

  return merge(left, right) # Gabungkan sub-array yang telah diurutkan

def merge(left, right):
  """
  Menggabungkan dua sub-array yang terurut menjadi satu array terurut.

  Args:
    left: Sub-array terurut di sebelah kiri.
    right: Sub-array terurut di sebelah kanan.

  Returns:
    Array terurut hasil penggabungan.
  """

  result = []
  i = j = 0

  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1

  # Tambahkan elemen yang tersisa dari sub-array kiri (jika ada)
  result += left[i:]
  # Tambahkan elemen yang tersisa dari sub-array kanan (jika ada)
  result += right[j:]

  return result

# Contoh penggunaan:
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print("Array yang diurutkan:", sorted_arr)

Penjelasan Kode:

• merge_sort(arr): Fungsi ini adalah fungsi rekursif utama yang mengimplementasikan algoritma Merge Sort.
  • Base Case: Jika panjang array kurang dari atau sama dengan 1, array tersebut sudah terurut dan dikembalikan langsung.
  • Recursive Step: Jika panjang array lebih dari 1, array dibagi menjadi dua sub-array (kiri dan kanan). Kemudian, fungsi merge_sort dipanggil secara rekursif untuk mengurutkan kedua sub-array tersebut. Setelah kedua sub-array terurut, fungsi merge dipanggil untuk menggabungkannya.
• merge(left, right): Fungsi ini bertanggung jawab untuk menggabungkan dua sub-array terurut (left dan right) menjadi satu array terurut.
  • Dua pointer (i dan j) digunakan untuk melacak posisi saat ini di masing-masing sub-array.
  • Elemen-elemen dari kedua sub-array dibandingkan, dan elemen yang lebih kecil ditambahkan ke array result.
  • Setelah salah satu sub-array selesai diproses, elemen-elemen yang tersisa dari sub-array lainnya ditambahkan ke array result.

Kompleksitas Waktu dan Ruang

• Kompleksitas Waktu: Merge Sort memiliki kompleksitas waktu O(n log n) dalam semua kasus (terbaik, rata-rata, dan terburuk). Hal ini menjadikannya algoritma pengurutan yang efisien, terutama untuk dataset besar.
• Kompleksitas Ruang: Merge Sort membutuhkan ruang tambahan O(n) karena membutuhkan ruang untuk menyimpan sub-array sementara selama proses penggabungan. Ini merupakan kelemahan potensial dibandingkan algoritma pengurutan in-place seperti Insertion Sort atau Heap Sort, terutama jika memori terbatas.

Kelebihan dan Kekurangan Merge Sort

Kelebihan:

• Performa yang konsisten: Memberikan kompleksitas waktu O(n log n) dalam semua kasus.
• Stabil: Mempertahankan urutan relatif dari elemen dengan nilai yang sama.
• Cocok untuk pengurutan dataset besar: Efisien dalam mengurutkan data dalam jumlah besar.
• Dapat diimplementasikan secara paralel: Proses pengurutan sub-array dapat dilakukan secara paralel, meningkatkan kinerja lebih lanjut.

Kekurangan:

• Membutuhkan ruang tambahan O(n): Kurang efisien dalam penggunaan memori dibandingkan algoritma in-place.
• Overhead rekursi: Panggilan rekursif dapat menambah overhead kinerja, terutama untuk dataset kecil.

Kapan Menggunakan Merge Sort?

Merge Sort adalah pilihan yang baik ketika:

• Performa yang konsisten dan dapat diprediksi lebih penting daripada penggunaan memori.
• Data yang akan diurutkan terlalu besar untuk dimuat ke dalam memori secara keseluruhan (pengurutan eksternal).
• Stabilitas diperlukan (urutan elemen yang sama harus dipertahankan).
• Parallelisme dapat dimanfaatkan untuk meningkatkan kinerja.

Alternatif untuk Merge Sort

Jika penggunaan memori merupakan pertimbangan utama, algoritma pengurutan in-place seperti Heap Sort atau Quick Sort mungkin lebih cocok. Namun, perlu diingat bahwa Quick Sort memiliki kompleksitas waktu terburuk O(n^2) dan tidak stabil.

Kesimpulan

Merge Sort adalah algoritma pengurutan yang kuat dan serbaguna yang menawarkan kinerja yang konsisten dan dapat diandalkan. Meskipun membutuhkan ruang tambahan, keunggulannya dalam hal efisiensi dan stabilitas menjadikannya pilihan yang tepat untuk berbagai aplikasi, terutama yang melibatkan dataset besar atau kebutuhan akan paralelisme. Memahami prinsip dasar dan implementasi Merge Sort akan membekali Anda dengan alat yang berharga dalam toolkit pengembangan perangkat lunak Anda. Ingatlah untuk mempertimbangkan kelebihan dan kekurangan Merge Sort relatif terhadap algoritma pengurutan lainnya untuk membuat keputusan yang tepat berdasarkan kebutuhan spesifik proyek Anda. Apakah Anda akan menggunakan Merge Sort dalam proyek berikutnya? Pertimbangkan kompleksitas data Anda dan batasan sumber daya yang Anda miliki.