Merge sort : Dev - Pascal

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)). Notasi O besar (big-O notation) atau notasi Landau adalah notasi matematika yang digunakan terutama pada bidang ilmu komputer (computer science). Notasi ini digunakan untuk menyatakan keefektifan sebuah alogatitma. Notasi ini bekerja dengan cara memperhitungkan input yang diberikan oleh user.

Cara Kerja Merge Sort seperti 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