Merge Sort

Algoritma Merge adalah algoritma yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data mu. Hal ini disebabkan algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

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.

Algoritma Merge umumnya memiliki satu set pointer p_0..n yang menunjuk suatu posisi di dalam satu set daftar L_0..n . Pada awalnya mereka menunjuk item yang pertama pada setiap daftar. Algoritmanya sebagai berikut:

Selama p_0..n masih menunjuk data yang di dalam sebagai pengganti pada akhirnya:

1. Melakukan sesuatu dengan data item yang menunjuk daftar mereka masing-masing.
2. Menemukan pointers points untuk item dengan kunci yang paling rendah; membantu salah satu pointer untuk item yang berikutnya dalam daftar.

Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer.

Algoritma untuk merge sort ialah sebagai berikut :

1. Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)

2. Untuk kasus n>1, maka :

a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.

b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian.

MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.

Contoh kasus:

Algoritma

Procedure MergeSort(input/output A : TabelInt, input i, j : integer)

{ Mengurutkan tabel A[i..j] dengan algoritma Merge Sort

Masukan: Tabel A dengan n elemen

Keluaran: Tabel A yang terurut

}

Deklarasi:

k : integer

Algoritma:

if i { Ukuran(A)> 1}

k←(i+j) div 2

MergeSort(A, i, k)

MergeSort(A, k+1, j)

Merge(A, i, k, j)

Endif