Algoritma merge sort membagi (split) table menjadi dua tabel sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk table yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah dibagi dua dan satu untuk menyimpan elemen yang telah teurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan. Di bawah ini adalah algoritma untuk merge sort yang dilakukan pada dua tabel.
Algoritma merge sort ini sebenernya lebih cepat dibandingkan heap sort untuk tabel yang lebih besar. Namun, algoritma ini membutuhkan setidakny ruang atau emori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel. Hal ini menyebabkan algoritma ini kurang banyak dipakai.
Tidak ada komentar:
Posting Komentar