Merge Sort

Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari konsep divide and conquer karena merge sort mengadaptasi pola tersebut.

Pola Divide and Conquer
   Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.

 

Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.
1. Divide
 Memilah masalah menjadi sub masalah
2. Conquer

 Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana,  pendekatan penyelesaian secara langsung akan lebih efektif
3. Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama 

 

Memahami Merge Sort

Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
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 .

 

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Algoritma
void mergeSort(Object array[], int startIdx, int endIdx) {
       if (array.length != 1) {
        //Membagi rangkaian data, rightArr dan leftArr
mergeSort(leftArr, startIdx, midIdx);
mergeSort(rightArr, midIdx+1, endIdx);
      combine(leftArr, rightArr);
    }
    }
Pengenalan