Urut gabung

**Urut 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. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

## Algoritma
Prinsip utama yang diimplementasikan pada algoritma urut gabung sering kali disebut sebagai *pecah-belah dan taklukkan* (bahasa Inggris: *divide and conquer*). Cara kerja algoritma 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 algoritma 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]  ***{3, 4, 9}*** dan ***{5}***
** ***{1, 2, 3}***  ***{4, 9}*** dan ***{5}***
** ***{1, 2, 3, 4}***  ***{9}*** dan ***{5}***
** ***{1, 2, 3, 4, 5}***  ***{9}*** dan ***{null}***
** ***{1, 2, 3, 4, 5, 9}***  ***{null}*** dan ***{null}***

## Pranala luar

*  Animated Sorting Algorithms: Merge Sort – graphical demonstration and discussion of array-based merge sort
*  Analyze Merge Sort in an online Javascript IDE
*  Merge sort applet  with level order recursive calls to help improve algorithm analysis
*  Dictionary of Algorithms and Data Structures: Merge sort
*  Implementation of merge sort in various languages on Rosetta Code
*  Literate implementations of merge sort in various languages  on LiteratePrograms
*  Implementation for C++
*  A colored graphical Java applet  which allows experimentation with initial state and shows statistics
*  Simon Tatham's explanation and code for a merge sort
*  MergeSort tutorial and Java code for beginners 
*  MergeSort in Java, Python, Perl, PHP, Ruby