Merge sort bilgisayar bilimlerinde yaygın olarak kullanılan bir sıralama algoritmasıdır. Böl ve fethet (divide and conqueror) şeklinde çalışan bu algoritma bir problemi doğrudan çözülebilene kadar küçük parçalara bölerek çalışır. Alt problemler çözümlere kavuştukça orjinal probleme çözüm bulabilmek adına geri birleştirme işlemi gerçekleştirilir.
Algoritma Adımları :
1- Veri listesini tekrar bölünemeyecek bir duruma gelene kadar böl. (Divide)
2- Küçük listeleri sıralı bir şekilde yeni bir listede sıralayarak birleştir. (Conqueror)
Örnek
Bir adet sayı dizimiz olsun. Bu sayı dizimiz sıralanmamış bir şekilde ve 8 elemandan oluşuyor. Sizlerle beraber bu sayı dizisini adım adım sıralayacağız. Hazırsanız başlayalım.
Algoritmamızın ilk adımında elimizdeki veri dizisini bölünemeyene dek parçalara ayırıyorduk. Listemiz 8 elemandan oluştuğu için zorlanmadan 4 – 4 şekilde listemizi ayırabiliriz. Lakin listemizin boyutu tek bir sayı olsaydı yarı yarıya bölünemeyecekti. Bunun için oluşacak iki listeden bir tanesi artan sayıyı üstlenecekti. Devam edelim.
Listemizi yarı yarıya böldük. Bitti mi ? Hayır, çünkü kuralımız sonuna kadar bölmek idi. Bütün adımları işleyip son durumun görünümünü sizlerle paylaşıyorum.
Bu adımdan sonra listelerimizi sıralayarak birleştiriyoruz.
Birinci listemiz ile ikinci listemiz, üçüncü listemiz dördüncü listemiz … şeklinde sıralanarak birleştirildi. Şu anda elimizde 4 liste kaldı. Bu dört listeyide ikişerli olarak birleştireceğiz.
Merge algoritması kullanarak sizler için bir adet Java ile örnek hazırladım. Kodları incelemek isterseniz linkten ulaşabilirsiniz.