Pengurutan gabungan adalah algoritma pengurutan yang efisien, bertujuan umum, dan berbasis perbandingan. Ini adalah paradigma algoritmik yang membagi dan menaklukkan yang dikembangkan oleh John von Neumann pada tahun 1945. Pengurutan gabungan bekerja dengan memecah daftar secara rekursif menjadi beberapa sub-daftar hingga setiap sub-daftar hanya terdiri dari satu elemen dan menggabungkan sub-daftar tersebut dalam sebuah urutan alami untuk menghasilkan daftar yang diurutkan.
Kompleksitas waktu proses pengurutan penggabungan dianggap optimal, artinya tidak dapat dilakukan lebih cepat daripada kompleksitas waktu O(n log n). Ini menjadikannya pilihan populer untuk menyortir kumpulan data besar. Pengurutan gabungan adalah algoritme pengurutan yang stabil, artinya algoritme ini mempertahankan urutan elemen duplikat dalam daftar yang diurutkan.
Pengurutan gabungan biasanya diimplementasikan menggunakan teknik iteratif, top-down, atau bottom-up. Dalam implementasi berulang, array tambahan dialokasikan, yang digunakan untuk menyimpan hasil antara saat daftar sedang diurutkan. Sebaliknya, pendekatan top-down menggunakan rekursi untuk memecah daftar menjadi kumpulan elemen yang lebih kecil, sedangkan pendekatan bottom-up menggunakan serangkaian operasi penggabungan yang melintasi data ke arah atas.
Algoritme ini memiliki banyak variasi, seperti pengurutan penggabungan empat arah, pengurutan penggabungan alami, dan pengurutan penggabungan polifase. Meskipun pengurutan gabungan lebih lambat dibandingkan quicksort, yang merupakan algoritma pengurutan lainnya, keuntungannya adalah waktu berjalan kasus terburuknya masih O(n log n). Hal ini membuatnya cocok untuk aplikasi yang mengutamakan efisiensi, seperti sistem tertanam, kumpulan data besar, dan pengurutan daftar dengan operasi daftar tertaut overhead.
Pengurutan gabungan digunakan secara luas dalam ilmu komputer, khususnya di bidang pengurutan, database, dan algoritma. Ini sering digunakan dalam sistem operasi untuk mengurutkan data seperti file dan folder dalam urutan yang bermakna, dan juga digunakan dalam pengembangan perangkat lunak untuk menyederhanakan proses pengembangan.
Pengurutan gabungan relatif mudah dipahami dan dikodekan, dan merupakan algoritme pengurutan yang berguna untuk dipelajari pemula sebagai pengenalan algoritme.
