Algoritma Sorting - Merge Sort

Image by OpenClipart-Vectors from Pixabay

Apa itu Merge Sort?

Merge Sort adalah algoritma Divide and Conquer. Algoritma Merge Sort membagi array input menjadi dua bagian. Secara terus menerus (recursive), memanggil fungsi dirinya sendiri untuk membagi array menjadi 2 bagian hingga didapat array berisi 1 elemen. Berikutnya dua bagian array tersebut diurutkan dan digabungkan secara bersamaan hingga membentuk 1 array yang telah terurut. Berikut visualisasi algoritma merge sort:

Source: Wikipedia

1. Ilustrasi warna merah: algoritma merge sort terus membagi array menjadi 2 bagian.
2. Ilustrasi warna abu-abu: algoritma telah selesai membagi array, dan didapat array berisi 1 elemen (Tidak bisa dibagi lagi). Pada contoh tersebut terdapat 7 array berisi 1 elemen.
3. Ilustrasi warna hijau: algoritma mulai membandingkan elemen dari ke 2 bagian array untuk diurut dan digabungkan.

Dibanding algoritma sorting lainnya seperti Bubble Sort, Insertion Sort, dan Selection Sort. Algoritma Merge Sort sangat cepat dan dapat digunakan untuk mengurutkan array dalam ukuran yang besar, dengan time complexity O(nLogn).

Implementasi Algoritma Merge Sort

Berikut implementasi algoritma Merge Sort di beberapa bahasa pemrograman:

Link github https://github.com/madeyoga/SortingAlgorithms

Semoga bermanfaat 🙏