Pengertian Merge Sort

Merge Sort adalah salah satu algoritma pengurutan yang digunakan dalam pemrograman. Algoritma ini merupakan metode yang efisien untuk mengurutkan sejumlah besar data dalam urutan tertentu. Merge Sort menggunakan pendekatan divide and conquer, dimana data yang akan diurutkan dibagi menjadi beberapa bagian yang lebih kecil, diurutkan secara terpisah, dan kemudian digabungkan kembali menjadi urutan yang benar.

Cara Kerja Merge Sort

Merge Sort bekerja dengan cara membagi data yang akan diurutkan menjadi dua bagian yang seimbang. Setelah itu, setiap bagian tersebut akan diurutkan secara terpisah dengan menggunakan rekursi. Setelah semua bagian terurut, langkah terakhir adalah menggabungkan kembali bagian-bagian tersebut menjadi satu urutan yang benar.

Proses Merge Sort dimulai dengan membagi data menjadi dua bagian seimbang. Jika jumlah data ganjil, maka dua bagian tersebut akan memiliki jumlah data yang berbeda satu. Selanjutnya, setiap bagian akan diurutkan secara terpisah dengan rekursi, yang berarti memanggil fungsi Merge Sort untuk setiap bagian secara terpisah. Fungsi Merge Sort akan terus membagi bagian-bagian tersebut hingga tinggal satu elemen dalam setiap bagian.

Setelah semua bagian terurut, langkah terakhir adalah menggabungkan kembali bagian-bagian tersebut menjadi satu urutan yang benar. Proses penggabungan dimulai dengan membandingkan elemen terkecil dari masing-masing bagian dan memindahkannya ke array hasil. Kemudian, elemen terkecil yang sudah dipindahkan akan dibandingkan kembali dengan elemen-elemen berikutnya hingga semua elemen telah dipindahkan ke array hasil. Dalam proses penggabungan, elemen-elemen diurutkan secara terus menerus hingga membentuk satu urutan yang benar.

Kelebihan dan Kekurangan Merge Sort

Kelebihan dari Merge Sort adalah:

1. Efisien dalam pengurutan data yang berukuran besar.

2. Mampu mengatasi kasus terburuk dengan kompleksitas waktu yang tetap (O(n log n)).

3. Stabil, artinya jika ada elemen yang sama, urutan relatif mereka akan tetap sama setelah diurutkan.

4. Cocok digunakan untuk data yang tidak dapat dimuat ke dalam memori utama.

Sementara itu, kekurangan dari Merge Sort adalah:

1. Membutuhkan ruang tambahan untuk menyimpan data sementara saat proses penggabungan.

2. Waktu eksekusi yang relatif lambat dibandingkan dengan beberapa algoritma pengurutan lainnya seperti Quick Sort atau Heap Sort.

3. Tidak efisien untuk data yang berukuran kecil.

Contoh Penerapan Merge Sort dalam Pemrograman

Contoh berikut adalah implementasi Merge Sort dalam bahasa pemrograman Python:

def merge_sort(arr):
if len(arr)