Urut gabung

Merge sort adalah alogirma yang digunakan untuk menyusun list yang diberikan dengan cara membagi list yang diberikan menjadi dua bagian yang lebih kecil. Kedua list yang baru ini kemudian akan disusun secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk list baru yang merupakan hasil penggabungan dua buah list sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O(nlog(n))

Beginilah cara kerja alogaritma ini:

Diberikan list yang ingin disusun:

3 9 4 1 5 2

List diatas dibagi menjadi dua bagian:

list 1:     |    list 2:
3 9 4       |    1 5 2

Kedua list yang baru disusun sendiri-sendiri menjadi:

list 1:     |    list 2:
3 4 9       |    1 2 5

Setelah itu dubentuk list baru yang merupakan gabungan kedua list tadi:

List baru:
1
list 1:     |    list 2:
3 4 9       |    2 5

List baru:
1 2
list 1:     |    list 2:
3 4 9       |    5

List baru:
1 2 3
list 1:     |    list 2:
4 9         |    5

List baru:
1 2 3 4
list 1:     |    list 2:
9           |    5

List baru:
1 2 3 4 5
list 1:     |    list 2:
9           |    kosong

List baru:
1 2 3 4 5 9
list 1:     |    list 2:
kosong      |    kosong

Dan akhirnya akan didapat list yang sudah tersusun:

List:
1 2 3 4 5 9