Merge sort adalah algoritma pengurutan yang menggunakan pendekatan divide and conquer. Algoritma ini membagi array yang akan diurutkan menjadi bagian-bagian yang lebih kecil, lalu mengurutkan bagian-bagian tersebut secara terpisah, dan kemudian menggabungkannya kembali menjadi array yang terurut.

Untuk mengurutkan nomor tiket kereta menggunakan algoritma merge sort, pertama-tama kita perlu membagi array yang akan diurutkan menjadi bagian-bagian yang lebih kecil. Kita bisa membagi array tersebut menjadi dua bagian yang sama besar, yaitu:

[10, 6, 18, 3]

[12, 4, 13, 27]

Kemudian, kita urutkan masing-masing bagian tersebut secara terpisah menggunakan algoritma merge sort. Proses pembagian dan pengurutan akan terus dilakukan sampai setiap bagian hanya terdiri dari satu elemen, yaitu:

[3, 6, 10, 18]

[4, 12, 13, 27]

Setelah setiap bagian terurut, kita kemudian menggabungkannya menjadi satu array yang terurut. Kita bisa menggunakan pendekatan "merge" untuk menggabungkan dua bagian terurut menjadi satu array yang terurut. Proses merge ini dilakukan dengan membandingkan elemen pertama dari setiap bagian, lalu menambahkan elemen yang lebih kecil ke dalam array yang baru. Proses ini akan terus dilakukan sampai semua elemen dari kedua bagian tersebut telah ditambahkan ke dalam array yang baru.

[3, 4, 6, 10, 12, 13, 18, 27]

Ilustrasi proses pengurutan menggunakan algoritma merge sort dapat dilihat pada gambar di bawah ini:

                                [10, 6, 18, 3, 12, 4, 13, 27]

                                 /                           \

                     [10, 6, 18, 3]                         [12, 4, 13, 27]

                      /            \                         /             \

            [10, 6]                 [18, 3]           [12, 4]              [13, 27]

             /    \                   /   \             /   \                /   \

       [10]        [6]         [18]        [3]    [12]        [4]      [13]       [27]

        |            |            |           |       |           |          |          |

        3            6            10          18       4           12         13         27

         \            \            \           /       \           /          /