Bir forumda şunları okudum :

Sıralama için çok verimli birleştirme değişmez datastructures bağlantılı gibi listeler

ve

Hızlı sıralama genellikle daha hızlıdır veri saklanır zaman sıralama birleştirme bellek. Veri ayarlandığında ancak, ve harici cihazlarda saklanan büyük bir sabit disk gibi, sıralama birleştirme hız açısından net kazanır. Bu bu pahalı okur en aza indirir harici disk

ve

bağlı listeler üzerinde çalışırken, birleştirmeli sıralama sadece yardımcı depolama küçük sabit bir miktar gerektirir

Biri bana yukarıdaki argüman anlamanıza yardımcı olabilir? neden onun gibi büyük bağlı listeler, sıralama için tercih edilen birleştirme? ve ne kadar pahalı harici bir diske okur küçültüyor mu? aslında büyük bir bağlı listeyi sıralamak için sıralama seçin birleştirme neden anlamak istiyorum.

Hızlı sıralama iyi yerinde sıralama için çalışıyor. Özellikle, operasyonların En bir dizideki öğelerin çiftleri takas açısından tanımlanabilir. Bunu yapmak için, ancak, normalde "" iki işaretçileri (veya dizinleri, vb.) ile dizinin içinden Sonunda bu dizi ve diğer başında başlar. Hem sonra ortada doğru yola (ve tanıştıkları zaman takılsa bir adım ile bitti. Bu dosyaları öncelikle başından sonuna kadar tek bir yönde okuma, yönelmiştir çünkü dosyaları pahalı. Sondan başlayıp geriye doğru arayan genellikle oldukça pahalıdır.

En azından basit cisimleşmiş, hemen hemen tersidir sıralama birleştirme. Bunu uygulamak için kolay yolu, sadece bir yöne verilere bakarak, gerektiriramaiki ayrı parçalar halinde veri kırarak, parçaları sıralama, sonra onları birleşmeye, geri içerir.

Bağlantılı bir liste ile, kolay (örneğin) bir bağlı liste içinde değişen elemanlar almak ve bağlantıları aynı elementlerden iki bağlantılı listeler yerine oluşturmak için işlemek için. Bir dizi, değişen öğeleri ayrı diziler böyle unsurlarını yeniden düzenleyerek bir kopyasını orijinal veri gibi büyük oluşturmak için istekli iseniz, ama aksi halde çok daha kolay ve önemsiz değil.

Aynı şekilde, birleştirme ile diziler kolay eğer birleştirme elemanları kaynak dizilerine yeni bir dizi ile verileri için -- ama bunun içinde yer almadan oluşturma tamamen yeni bir kopyasını veri tamamen farklı bir hikaye. Bağlantılı bir liste ile, tek bir hedef listesine iki kaynak listelerden birlikte öğeleri birleştirme önemsiz -- yine, bağlantılar, elemanları kopyalamadan işlemek.

Quicksort kullanarak bir dış birleştirme sıralama için sıralama üretmek için çalışır, çalışır, ama (kesinlikle) bir kural olarak alt-optimal. A-sıralama birleştirme optimize etmek için, normalde her "üretmek gibi." run sıralanmış uzunlukları en üst düzeye çıkarmak istiyoruz Eğer sadece hafıza uyum, Quicksort ve bunu yazacak olan verileri okumak, her çalışma için (daha az) kullanılabilir bellek boyutu sınırlı olacak.

Biraz daha iyi bir kural gibi olsa yapabilirsin. Veri bloğu okuyarak başlamak, ama bir Quicksort kullanmak yerine, bir yığın oluşturun. Her madde sıralanmış içine yığınından yazmak gibi "" dosyasını okuyun . çalıştırın ^em>başka birmadde giriş dosyası. Eğer maddenin daha büyük sadece disk, mevcut yığın takın ve tekrar yazdı.

Küçük öğeler (örneğin, daha önce yazılmış olan öğeleri önce ait) ayrı tutmak ve inşa ikinci bir yığın halinde. Ne zaman (ve sadece) ilk yığın boş ve ikinci yığın var ele tüm bellek, çıkın yazma öğeleri mevcut "run" dosyası ve başlangıç yeni bir tane.

Tam olarak bunun ne kadar etkili olacak verilerin ilk sırasına bağlıdır. En kötü durum (giriş ters sırada sıralanır), hiç de güzel değil. En iyi durum (giriş zaten sıralanmış) "" giriş sayesinde tek bir çalışma içinde. verileri sıralamak sağlar Ortalama bir dava (rastgele giriş) genellikle hızını artıracak sıralanmış her çalışma, yaklaşık iki katı uzunlukta sağlaretrafında20-25% yüzdesi daha büyük veri mevcut hafızanın daha ne kadar bağlı olarak değişir.