Birleştirme sıralaması

Merge sort, 1945 yılında John von Neumann tarafından geliştirilen bir sıralama algoritmasıdır. Büyük bir listeyi verimli bir şekilde iki küçük alt listeye bölmek, alt listeleri özyinelemeli olarak sıralamak ve ardından sonuçları tek bir sıralanmış liste halinde birleştirmek için böl ve yönet yaklaşımını kullanan verimli, genel amaçlı, karşılaştırma tabanlı bir sıralama algoritmasıdır. Merge sort kararlıdır, yani listedeki eşit öğelerin orijinal sırasını korur.

Algoritma

Merge sort aşağıdaki adımları izleyerek çalışır:

1. Bölme: Sıralanmamış listeyi kabaca eşit büyüklükte iki alt listeye bölün
2. Fethetmek: Her bir alt listeyi özyinelemeli olarak sırala
3. Birleştir: Sıralanmış iki alt listeyi tekrar sıralanmış tek bir liste halinde birleştirin

Birleştirme işlemi, iki küçük sıralanmış listeyi alıp daha büyük bir sıralanmış liste oluşturmak için bunları birleştirmeyi içerir. Her adımda, her iki alt listeden en küçük eleman alınır ve sonuç dizisine yerleştirilir. İşlem daha sonra tüm alt listeler tek bir sıralanmış sonuçta birleştirilene kadar tekrarlanır.

Performans

Merge sort O(n log n) zaman karmaşıklığına sahiptir, yani girdinin boyutu ile doğrusal olarak ölçeklenir. Büyük listeleri sıralamak için çok uygundur ve aynı zamanda kararlıdır, yani eşit öğelerin sırasını korur. Dezavantajı ise, alt listeleri saklamak için ek depolama alanı gerektirmesi ve bu nedenle daha küçük listeler veya yerinde sıralama için daha az verimli olmasıdır.

Sonuç

Merge sort, kararlı, verimli ve anlaşılması kolay olan iyi bilinen bir sıralama algoritmasıdır. Çok çeşitli veri türlerini sıralamak için uygundur ve büyük listeleri doğrusal zamanda sıralayabilir. Düşük alan karmaşıklığı onu birçok uygulama için ideal bir seçim haline getirir.