A new merge based sort algorithm for nearly sorted lists

Abstract

Sıralama algoritmalarının performansı, özellikle büyük boyutta verilerin işlendiği sistemlerde, arama gibi temel algoritmaların daha performanslı gerçekleştirilebilmesinin ön koşulu olduğu için büyük önem taşımaktadır.Sık kullanılan sıralama algoritmaları (Örn; HeapSort, MergeSort) eldeki verinin karakteristik özellikleri dikkate alınmadan oluşturulmuş genel sıralama algoritmalarıdır. Verinin karakteristik özelliklerinin (Örn: Sıralanmışlık) bilinebildiği durumlarda, bu durumlara özel daha performanslı çözümler üretilebilir.Bu çalışmada, bu zamana kadar bulunan sıralama algoritmalarından, bu çalışmaya temel oluşturacak yöntemleri içeren algoritmalar incelenmiştir. Ayrıca çalışmanın temelini oluşturduğu için, şimdiye kadar kullanılmış birleştirme (merge) işlemlerine de değinilmiş, sonrasında da incelenen yöntemlerin sıralıya yakın diziler için uyarlanabilir hale gelmesi için iyileştirmeler yapılmaya çalışılmıştır.

Methods and algorithms, i.e. sorting algorithms, can be customized to increase system performance in large data systems. In order to do this, various parameters like data flow or data characteristics must be known.Widely used sorting algorithms (e.g., HeapSort, MergeSort) do not consider the characteristics of data and introduce general solutions for almost all cases. Better performance algorithms can be found when some parameters (e.g., Sortedness) taken into account.In this work, first the sorting algorithms which can provide a basis for the new method are reviewed. Also, because the new method is merge based, former merge algorithms are reviewed. Finally, based on the former methods, new sorting method is presented for nearly sorted lists.