Urut gabungUrut gabung atau sering juga disebut dalam istilah Inggrisnya merge sort merupakan algoritme 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. Algoritme ini ditemukan oleh John von Neumann pada tahun 1945. AlgoritmePrinsip 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 merge( input_tape, output_tape, scratch_tape_C) merge( input_tape, output_tape, scratch_tape_D) while any records remain on C or D merge( scratch_tape_C, scratch_tape_D, output_tape) merge( scratch_tape_C, scratch_tape_D, input_tape) # take the next sorted chunk from the input tapes, and merge into the single given output_tape. # tapes are scanned linearly. # tape[next] gives the record currently under the read head of that tape. # tape[current] gives the record previously under the read head of that tape. # (Generally both tape[current] and tape[previous] are buffered in RAM ...) function merge(left[], right[], output_tape[]) do if left[current] ≤ right[current] append left[current] to output_tape read next record from left tape else append right[current] to output_tape read next record from right tape while left[current] < left[next] and right[current] < right[next] if left[current] < left[next] append current_left_record to output_tape if right[current] < right[next] append current_right_record to output_tape return Contoh penerapan atas sebuah larik sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:
Pranala luar
|