Minggu, 26 Januari 2014
Merge sort adalah algoritma yang berjalan dengan waktu O(N log N), yang jauh lebih efisien daripada O(N^2), dan akan berjalan jauh lebih cepat untuk N yang besar.
Algoritma merge sort sesungguhnya sangat sederhana: Bagi array menjadi dua sama besar, sort bagian pertama, sort bagian kedua, lalu gabungkan. Tentu sort ini menggunakan prosedur rekursif dengan parameter index paling kiri (a) dan index paling kanan (b).
procedure
sort(terkiri,terkanan:longint);
begin
if terkiri < terkanan then
begin
sort(terkiri,(terkiri+terkanan) div 2);
sort(((terkiri+terkanan) div 2) + 1,
terkanan);
merge(terkiri,(terkiri+terkanan) div 2,
((terkiri+terkanan) div
2)+1,terkanan);
end;
end;
