Jelaskan Algoritme dari Urut gabung

Prinsip utama yang diimplementasikan pada algoritme urut gabung sering kali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Cara kerja algoritme urut gabung adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O(nlog(n)). Dalam bentuk pseudocode sederhana algoritme ini dapat dijabarkan sebagai berikut:

# Original data is on the input tape; the other tapes are blank

function merge_sort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)

while any records remain on the input_tape

while any records remain on the input_tape