Perbandingan
Penulisan
Penggabungan

  • Bagian yang digabung
  • Dibandingkan
  • Ditulis kembali
  • Sudah digabung

Info lebih lanjut tentang merge sort

Merge sort

Merge sort adalah algoritma divide and conquer. Algoritma ini membagi daftar menjadi dua, mengurutkan setiap paruh dengan cara yang sama, lalu menggabungkan dua paruh yang terurut dengan berulang kali mengambil nilai terdepan yang lebih kecil. Saksikan paruh-paruh dipindahkan ke baris buffer lalu ditulis kembali secara berurutan, dengan kecepatan berapa pun atau selangkah demi selangkah, dan hitung perbandingan, penulisan, serta penggabungan. Tekan Putar untuk melihat pengurutan, atau Langkah dan Mundur untuk maju satu langkah setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Kotak-kotak menghitung perbandingan, penulisan kembali ke daftar, dan penggabungan. Pilih jumlah batang, urutan awalnya, atau ketik angka sendiri. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Pilih jumlah batang dan urutan awalnya: acak, hampir terurut, terbalik, atau dengan sedikit nilai unik. Atau ketik angka sendiri.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu langkah setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pengurutan.
  3. Amati setiap penggabungan: dua paruh yang terurut turun ke buffer, dan nilai terdepan yang lebih kecil naik kembali, satu per satu.

Cara kerja merge sort

Satu nilai sudah pasti terurut. Untuk yang lebih panjang, bagi daftar menjadi dua paruh dan urutkan setiap paruh dengan merge sort. Lalu gabungkan: lihat nilai terdepan setiap paruh, pindahkan yang lebih kecil ke hasil, dan ulangi sampai kedua paruh kosong. Karena kedua paruh terurut, hasilnya juga terurut.

Selalu n log n

Membagi dua terus-menerus menghasilkan sekitar log₂ n tingkat, dan setiap tingkat penggabungan menulis setiap nilai sekali, jadi pengurutan melakukan sekitar n log₂ n penulisan, dan paling banyak sejumlah itu pula perbandingannya. Tidak seperti bubble sort, selection sort, dan insertion sort, jumlah itu tidak tumbuh seiring n², dan urutan daftar jauh kurang berpengaruh. Harganya adalah buffer sepanjang daftar. Merge sort juga stabil, karena itulah ia menjadi dasar pengurutan di Python dan Java.

Pertanyaan yang sering diajukan

Bagaimana cara kerja merge sort?

Merge sort membagi daftar menjadi dua, mengurutkan setiap paruh dengan merge sort, lalu menggabungkan kedua paruh yang terurut dengan berulang kali mengambil yang lebih kecil dari nilai terdepannya. Daftar berisi satu nilai sudah terurut, jadi pembagian berhenti di situ.

Berapa banyak perbandingan yang dilakukan merge sort?

Untuk n nilai, paling banyak sekitar n log₂ n − n + 1, dan paling sedikit sekitar setengah dari n log₂ n. Untuk 40 nilai, paling banyak 177. Jumlah penulisan kembali ke daftar selalu sama untuk n tertentu: satu per nilai di setiap tingkat penggabungan.

Mengapa merge sort butuh memori tambahan?

Menggabungkan dua paruh di tempat sulit dilakukan dengan cepat, jadi merge sort biasa menyalin paruh-paruh itu ke buffer dan menuliskannya kembali secara berurutan. Buffer itu sepanjang daftar, dan inilah kelemahan utamanya dibanding quicksort dan heap sort.

Apakah merge sort stabil?

Ya. Jika dua nilai terdepan sama, yang dari paruh kiri didahulukan, sehingga nilai yang sama tetap pada urutan aslinya.

Apakah angka saya dikirim ke mana pun?

Tidak. Pengurutan berjalan di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor