Birleştirmeli sıralama
Listeyi ikiye böler, her yarıyı sıralar, sonra sıralı iki yarıyı birleştirip tek bir sıralı liste yapar.
- en iyi Ω(n log n)
- ortalama Θ(n log n)
- en kötü O(n log n)
- bellek O(n)
- kararlı
- ek bellek ister
Bunlar ne demek?
- En iyi durum: girdi bu algoritma için en kolay olduğunda sürenin liste boyutu n ile nasıl arttığı.
- Ortalama: sürenin n ile olağan artışı. n²'de değer sayısı iki katına çıkınca süre yaklaşık dört katına çıkar; n log n çok daha yavaş artar.
- En kötü durum: en zor girdideki artış. Hızın asla düşmemesi gerektiğinde işe yarar.
- Bellek: listenin dışında ne kadar ek bellek gerektiği. 1 birkaç değişken, n listenin bir kopyası demektir.
- Kararlı: eşit iki değer başlangıçtaki sıralarını korur. Kayıtlar tek bir alana göre sıralanırken önemlidir.
- Ek bellek istemez: ikinci bir liste olmadan, listenin kendi içinde sıralar.
- karşılaştırılıyor
- taşınıyor
- son yerinde
Oynat'a basın: çizgiler maliyetin nasıl arttığını gösterir
Oynat tuşuna basın veya algoritmada adım adım ilerleyin.
Boşluk: oynat veya duraklat. Sol ve sağ oklar: adım adım. Home ve End: atla.
Şunu deneyin: Az sayıda farklı değer olan bir liste seçin. İki değer eşitse önce sol yarıdaki alınır, böylece eşit değerler sıralarını korur.
Nasıl çalışır
Liste, her parçada tek değer kalana kadar bölünür. Tek değerli parça zaten sıralıdır. Sonra parçalar ikişer ikişer birleştirilir: iki parçanın ilk değerleri karşılaştırılır ve küçük olan alınır, bu tekrar tekrar yapılır. Animasyonda yukarı kalkan satır, birleştirme sırasında kullanılan ek bellektir.
Ne zaman iyi bir seçimdir
En kötü durumda bile hızın iyi kalması ve eşit değerlerin sırasını koruması gerektiğinde. Hem Python hem Java birleştirmeli sıralamanın bir türünü kullanır. Dezavantajı, ihtiyaç duyduğu ek bellektir.