Gabungkan semacam

Merge sort adalah algoritme pengurutan yang dikembangkan oleh John von Neumann pada tahun 1945. Ini adalah algoritme pengurutan berbasis perbandingan yang efisien, bertujuan umum, dan menggunakan pendekatan bagi-dan-taklukkan untuk membagi daftar besar secara efisien menjadi dua sub-daftar yang lebih kecil, mengurutkan sub-daftar secara rekursif, lalu menggabungkan hasilnya kembali menjadi satu daftar yang diurutkan. Pengurutan gabungan bersifat stabil, artinya mempertahankan urutan asli elemen yang sama dalam daftar.

Algoritma

Penggabungan pengurutan berfungsi dengan mengikuti langkah-langkah berikut:

1. Bagi: Pisahkan daftar yang belum disortir menjadi dua sub-daftar yang ukurannya kira-kira sama
2. Taklukkan: Urutkan setiap sub-daftar secara rekursif
3. Gabungkan: Menggabungkan kembali dua sub-daftar yang telah diurutkan menjadi satu daftar yang telah diurutkan

Proses penggabungan melibatkan pengambilan dua daftar kecil yang diurutkan dan menggabungkannya untuk membentuk daftar terurut yang lebih besar. Pada setiap langkah, elemen terkecil diambil dari salah satu subdaftar dan ditempatkan ke dalam larik hasil. Proses tersebut kemudian diulangi hingga semua sub-daftar digabungkan menjadi satu hasil yang diurutkan.

Pertunjukan

Pengurutan gabungan memiliki kompleksitas waktu O(n log n), artinya skalanya linear dengan ukuran masukan. Ini sangat cocok untuk mengurutkan daftar besar, dan juga stabil, artinya mempertahankan urutan elemen yang sama. Sisi negatifnya, memerlukan ruang penyimpanan tambahan untuk menyimpan sub-daftar, sehingga kurang efisien untuk daftar yang lebih kecil atau penyortiran di tempat.

Kesimpulan

Merge sort adalah algoritma pengurutan terkenal yang stabil, efisien, dan mudah dipahami. Sangat cocok untuk mengurutkan berbagai tipe data, dan dapat mengurutkan daftar besar dalam waktu linier. Kompleksitas ruangnya yang rendah menjadikannya pilihan ideal untuk banyak aplikasi.