Menggabungkan Dua Urutan Terurut

Diberikan dua daftar terurut, gabungkan keduanya menjadi satu daftar terurut. Penggabungan ini adalah inti dari sort gabung dan muncul di berbagai tempat. 🔗

Berikan setiap daftar satu penunjuk, keduanya dimulai dari indeks 0. Anda akan menggerakkannya maju bersama-sama, tidak pernah mundur.

Pada setiap langkah, bandingkan kedua elemen terdepan. Tambahkan yang lebih kecil ke hasil karena elemen itu harus muncul berikutnya dalam urutan terurut.

Setelah mengambil sebuah nilai, lakukan advance hanya pada penunjuk asal nilai tersebut. Daftar lainnya masih memiliki elemen terkecil yang menunggu.

Teruskan penggabungan selama kedua daftar masih memiliki elemen. Setelah salah satunya habis, perbandingan tidak lagi masuk akal.

Saat salah satu daftar kosong, daftar lainnya sudah terurut, jadi cukup lakukan append pada sisa bagian belakangnya langsung ke hasil.

Sisa bagian belakang sudah terurut, jadi tidak diperlukan perbandingan lagi. Salah satu dari dua pemanggilan extend itu cukup menambahkan elemen, sedangkan yang lainnya tidak menambahkan apa pun.

Setiap elemen diperiksa satu kali, sehingga penggabungan dua daftar berukuran n dan m memerlukan waktu O(n + m). Itulah waktu tercepat yang dapat dicapai.

Menggunakan <= saat nilai sama akan mempertahankan elemen-elemen yang sama dalam urutan aslinya. Stabilitas ini penting saat Anda membawa data tambahan.

Untuk menggabungkan ke penyangga tanpa ruang kosong tambahan, telusuri dari belakang dan tempatkan elemen terbesar di posisi terakhir. Gagasannya sama, hanya dicerminkan.

Pecah, urutkan kedua bagian, lalu gabungkan: rekursi tersebut adalah sort gabung. Penggabungan dengan dua penunjuk yang baru Anda pelajari adalah mesin intinya.

Telusuri dua daftar terurut dengan masing-masing satu penunjuk, selalu mengambil elemen terdepan yang lebih kecil, lalu kuras sisa bagian belakangnya. Algoritme ini berjalan dalam O(n + m) dan menjadi dasar sort gabung. 🚀