Karıştırma tabanlı yerinde birleştirme algoritmalarının karşılaştırmalı performans analizi
Bildiriler > Tam Metin Bildiri · 2026
Yazarlar: Mehmet Emin DALKILIÇ, Serenay BARS
7th International Eurasian Conference on Science, Engineering and Technology (EurasianSciTech 2026), Türkiye, Ankara, Uluslararası, Sözlü Sunum, Tam Metin Bildiri, 2026-2026, ss 381-389
Özet
<p class="ql-align-justify">Birleştirme Sıralama (Merge Sort), en yaygın olarak kullanılan ve optimal O(n log n) zaman karmaşıklığına sahip bir sıralama algoritmasıdır. Bu algoritmanın en önemli avantajları kararlı olması ve önbellek uyumlu olmasıdır. En önemli dezavantajı ise O(n) ek bellek kullanımı gerektirmesidir. Yerinde birleştirme algoritmaları bu ek bellek kullanımını en aza indirmeyi ya da tümüyle kaldırmayı amaçlar. Literatürde yerinde birleştirme algoritmaları; ayrıştırma tabanlı, iç tampon tabanlı ve karıştırma tabanlı olmak üzere üç ana kategoride incelenmektedir. Bu üç yaklaşım arasında en yeni olanı karıştırma tabanlı yöntemler olup aynı zamanda üzerinde en az araştırma yapılmış olanıdır. Bu alanda literatürde yalnızca iki algoritmaya yer verilmektedir: ilki 2000 yılında Ellis ve Markov (EM2000), ikincisi ise 2011 yılında Dalkilic, Acar ve Tokatli (DAT2011) tarafından önerilmiştir. Bu çalışmada söz konusu iki algoritma Java programlama dili ile gerçeklenmiş; karşılaştırma sayısı, taşıma sayısı ve çalışma zamanı ölçütleri temel alınarak karşılaştırmalı bir performans analizi gerçekleştirilmiştir. Elde edilen sonuçlar, her iki algoritmanın hem bağımsız birer yerinde birleştirme algoritması olarak hem de Birleştirme Sıralama algoritmasının temel bileşeni olarak ortalama durum performansını kapsamlı biçimde ortaya koymaktadır. Öne çıkan bulgular, DAT2011 birleştirme algoritmasının ortalama karşılaştırma sayısının doğrusal düzeyde (O(n)) seyrettiğini; buna karşın taşıma sayısının süper polinomiyal bir büyüme sergilediğini (O(n¹·⁴³)) ve bu algoritmayı temel alan Birleştirme Sıralama algortimasının zaman karmaşıklığının ise O(n√n) olduğunu ortaya koymaktadır. EM2000 birleştirme algoritmasında ise ortalama durumda hem karşılaştırma hem de taşıma sayılarının O(n log log n) düzeyinde olduğu; test edilen 2⁸ – 2²⁴ problem boyutu aralığında, bu algoritmayı temel alan Birleştirme Sıralama algoritmasının zaman karmaşıklığının O(n log²n) olarak gerçekleştiği görülmüştür. Bu sonuçlar, karıştırma tabanlı yerinde birleştirme algoritmalarının pratik</p><p class="ql-align-justify"> kullanım açısından ümit vaat ettiğine işaret etmektedir.</p><p></p>