Algoritma
Merge Sort ditemukan oleh John vonNeumann di tahun
1945. Merge Sort termasuk paradigma algoritma divide and conquer
(kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma
ini melakukan pembagian struktur data sebelum kemudian dioperasi satu
per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai
berikut,
- Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
- Untuk
membentuk sebuah list terurut dari duabuah list terurut membutuhkan
langkah yangl ebih sedikit daripada membentuk sebuah list terurut dari
dua buah list tak terurut. Contoh:hanya diperlukan satu kali traversal
untuk masing-masing list jika keduanya sudahterurut.
Algoritma Merge Sort sederhananya, dapat ditulis berikut:
- Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.
- Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
- Gabung 2 sublist kembali menjadi satu list terurut.
Sumber: Buku Algoritma dan Pemrograman
Tidak ada komentar:
Posting Komentar