ve sonra büyük bir sıralı dosya içine geri bunları birleştirmek birleştirme birleştirme. birleştirirkençok yönlü 2 yönlü vs biz <a href="http://en.wikipedia.org/wiki/External_sorting" rel="nofollow">externally merge sort</a> bir büyük dosya sort'u o küçük olanlar, bölmek
, birçok birleştirme geçer 2 yönlü ya da bir çok-yollu birleştirme yapmak ya.
Hangi yaklaşımın daha iyi olduğunu merak ediyorum? ve neden?
Çok yönlü birleştirme genellikle daha iyidir. Düşünün üç küçük dosyalar:
a1
a2
a3
ve
b1
b2
b3
ve son olarak
c1
c2
c3
Eğer a ve b ile birleştirmek, biz (diyelim)
a1
b1
a2
b2
b3
a3
ve
c1
c2
c3
Son bir birleştirme sıralanmış liste oluşturmak, ancak bu son birleştirmede yine a ve b öğeleri ziyaret etmek nasıl fark ederdi. Bu, iki yönlü birleşmelerde savurgan olan yeniden birleşme. Bunun yerine yapabilecekleriniz
tek çok yönlü birleştirme olduğunu. Ancak, nasıl yaptığınıza dikkat edin. Özellikle, her bir imleci taranan ve minimum değere sahip olan saf çift döngüden kaçının. Bunun yerine bir min-yığın kullanın. Bu geri aşağı O(n log n) karmaşıklık getirecektir.