Merge Sort

Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

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.

Merge sort menggabungkan dua ide utama untuk meningkatkan runtimenya:

1. Array kecil akan mengambil langkah-langkah untuk menyortir lebih sedikit dari array besar.
2. Lebih sedikit langkah yang diperlukan untuk membangun sebuah array terurut dari dua buah array terurut daripada dari dua buah array tak terurut.

Dalam bentuk pseudocode, algoritma Merge Sort dapat terlihat seperti ini:

procedure mergesort(input n : integer,
input/output S : array[1..n] of
keytype)
{Mengurutkan array sebesar n dengan
urutan takmenurun
I.S. : n bilangan bulat positif, S
terdefinisi berindex dari 1 sampai n
F.S. : array S berisi elemen dengan
urutan takmenurun
}
const
h = n div 2
m = n – h
var
U : array [1..h] of keytype
V : array [1..m] of keytype
begin
if n > 1 then
copy dari S[1] hingga S[h] ke U
copy dari S[h+1] hingga S[n] ke V
mergesort(h,U)
mergesort(m,V)
merge(h,m,U,V,S)
end
end
procedure merge(input h,m : integer, U
: array [1..h] of keytype, V : array
[1..m] of keytype, input/output S :
array [1..h+m] of keytype)
{Menggabungkan dua array terurut
menjadi satu array terurut
I.S. : h dan m bilangan bulat positif,
array terurut U berindeks dari 1 sampai
h, array terurut V berindeks dari 1
sampai m
F.S. : array S berindex dari 1 sampai
h+m berisi elemen U dan V yang telah
terurut
}
var
i,j,k : indeks;
begin
i = 1
j = 1
k = 1
while i<=h and j<=m do
if U[i]<V[j] then
S[k]=U[i]
i = i + 1
else
S[k] = V[j]
j = j+1
k = k + 1
end
if i>h then
copy V[j] sampai V[m] ke S[k]
sampai S[h+m]
else
copy V[i] sampai U[h] ke S[k]
sampai S[h+m]
end

end

Pada umumnya algoritma merge berjalan dalam waktu proposional untuk penjumlahan pada panjangnya daftar; Algoritma merge beroperasi pada bilangan besar dalam daftar yang akan segera mengalikan penjumlahan panjangnya daftar pada saat itu untuk keluaran gambar pointers points yang mana menunjuk pada item yang paling rendah, yang dapat terpengaruhi dengan suatu heap(tumpukan) yang didasarkan prioritas antrian dalam O(lg n) waktu, untuk O(m lg n) waktu (dimana n adalah bilangan pada daftar yang digabungkan, m adalah penjumlahan panjangnya daftar, dan lg adalah log basis 2). Ketika menggabungkan panjang m dua daftar, terdapat suatu perbandingan lompatan yang lebih rendah 2m-1 yang ada dalam kasus terburuk.

Keluaran data item Merge klasik (satu yang digunakan dalam merge sort) dengan kunci yang paling rendah pada langkah masing-masing, memberikan beberapa daftar yang diurutkan, hasil daftar yang diurutkan berisi semua unsur-unsur di dalam daftar input manapun, dan hal itu dilakukan agar waktunya proporsioal untuk input penjumlahan panjangnya daftar.

Penggabungan dapat juga digunakan untuk berbagai hal:

• Diberikan satu set saldo-saldo rekening yang beredar dan satu set transaksi, kedua-duanya disortir oleh nomor rekening, menghasilkan satu saldo-saldo rekening baru setelah transaksi diterapkan; ini selalu diperlukan untuk mempercepat ”transaksi baru” penunjuk ketika keduanya mempunyai kunci yang sama, dan menambahkan semua angka-angka pada tape yang manapun dengan nomor rekening yang sama untuk menghasilkan saldo yang baru.
• Menghasilkan suatu daftar catatan yang disortir dengan menyajikan kunci disemua daftar ini yang memerlukan outputting kapan saja suatu catatan yang semua kunci p_0..n adalah sama.
• Dengan cara yang sama untuk menemukan bilangan besar pada satu tape yang lebih kecil dibandingkan masing-masing nomor pada satu tape yang lainnya (contoh untuk mengeluarkan gambar pengelompokan pajak masing-masing orang di dalamnya).
• Dengan cara yang sama untuk menghitung perbedaan set semua arsip dalam satu daftar dengan arsip yang tidak sesuaian dengan yang lainnya.
• Operasi penyisipan dalam mesin pencarian untuk menghasilkan suatu indeks balikkan.
• Menggabungkan permainan-permainan adalah suatu peranan pusat dalam fungsi pemrograman teknik Dijkstra untuk menghasilkan bilangan-bilangan tetap.

sehingga dapat disimpulkan bahwa, Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. 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.