Merge sort adalah sort yang dilakukan dengan teknik merge (menggabungkan) dua buah array kedalam sebuah array yang baru. Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.
Langkah kerja dari Merge sort secara umum:
1. Divide, Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer, Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif.
3. Kombinasi, Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Perbandingan Merge Sort dengan Quick Sort (O(n))
Di salah satu forum QUORA Martin Puryear (SW Engineer at Google) mengatakan bahwa Merge Sort lebih stabil dibandingkan Quick Sort terkecuali di kasus yang jumlah datanya terlalu besar maka Merge Sort akan membutuhkan memori yang besar.
Pengujian:
Pengujian merge sort dengan matriks 5000x5000
(proses paralel dilakukan dengan 2 core prosesor)
Link Source Code: