Pengurutan gabung
Membagi daftar menjadi dua, mengurutkan tiap separuh, lalu menggabungkan keduanya menjadi satu daftar terurut.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- ya
- tidak
Kasus terbaik: bagaimana waktu tumbuh seiring ukuran daftar n saat input paling mudah bagi algoritma ini.
Rata-rata: pertumbuhan waktu biasa terhadap n. Pada n², jumlah nilai 2 kali lipat butuh sekitar 4 kali waktu; n log n jauh lebih lambat.
Kasus terburuk: pertumbuhan pada input tersulit. Berguna saat kecepatan tidak boleh turun.
Memori: berapa memori tambahan yang dibutuhkan selain daftar. 1 berarti beberapa variabel, n berarti salinan daftar.
Stabil: dua nilai yang sama tetap dalam urutan aslinya. Penting saat mengurutkan data menurut satu kolom.
Tanpa memori tambahan: mengurutkan di dalam daftar itu sendiri, tanpa daftar kedua.
- dibandingkan
- dipindahkan
- di posisi akhir
Coba ini: Pilih daftar dengan banyak nilai sama. Jika dua nilai sama, yang dari separuh kiri diambil lebih dulu, jadi urutan nilai yang sama tetap.
Cara kerjanya
Terus bagi daftar sampai tiap potongan berisi satu nilai, yang pasti sudah terurut. Lalu gabungkan potongan itu berpasangan: bandingkan nilai pertama dari kedua potongan dan ambil yang lebih kecil, terus begitu. Baris yang terangkat di animasi adalah memori tambahan yang dipakai saat menggabungkan.
Kapan ini pilihan yang tepat
Saat Anda butuh kecepatan yang tetap baik bahkan di kasus terburuk, dan nilai yang sama harus tetap pada urutan semula. Python dan Java sama-sama memakai versi pengurutan gabung. Kelemahannya adalah memori tambahan yang dibutuhkan.