Bu soru çok özel olmadığını biliyorum.

İstediğim her yerde birleştirme tür bir (ya da bir sabit ekstra alan ile sıralama üstten birleştirme) birleştirme normal bir tür dönüştürmek için ne yapmam gerektiğini söyleyen biri.

Bulabildiğim tüm (net) sayfaları söyleyerek, "çok karmaşık" ya da "bu yazının kapsamı dışında".

Birleştirme için bilinen tek yolu yerinde (herhangi bir ekstra boşluk olmadan) pratik program ciddi bir düşüş olması için çok karmaşık. (from here alınan)

Eğer çok karmaşık değilse bile,yerinde sıralama birleştirme yapmak için nasıl temel kavramı nedir?

Onun "büyük sonuç", bu kağıt yerinde türevleri birkaç açıklanır sıralama birleştirme (PDF): dahil

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

-Daha az hareket eder sıralama

Jyrki Katajainen, Tomi A. Pasanen

N bir dizi gösterilmiştir elemanları O(1)kullanarak sıralanabilir ekstra alan, O(n log n / log n) öğe taşır ve n log 2 n O(n log günlük n) karşılaştırmaları. Bu ilk kez oldu yerinde sıralama algoritması gerektiren o(n log n) en kötü durumda hamle garanti O(n log n)ise karşılaştırmalar, ama sürekli bağlı faktörler algoritması dahil teorik ilgi ağırlıklı olarak.

Bu konuyla alakalı olduğunu da düşünüyorum. Ortalıkta, bana bir meslektaşım tarafından iletilen bir çıktısını aldım, ama okumadım. Temel teori kapsayacak gibi görünüyor, ama kapsamlı ne kadar hakim konuya yeterince aşina değilim:

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

Optimal Kararlı Birleştirme

Antonios Yakınında Symvonis

Bu kağıt nasıl gösterir stabil birleştirme boyutlarda iki dizileri ve A B m ve Ç ile n, m n, n, sırasıyla, (m n) atamalar, O(mlog(m 1 n/)) karşılaştırmalar ve tek bir sabit kullanarak ek alanı miktarı. Bu sonuç tüm alt sınırları bilinen kibrit