Birleştirmeli Sıralama (Merge Sort) Nedir ?

Birleştirme sıralama(Merge sort) algoritması adından da anlaşılacağı üzere bir sıralama algoritmasıdır. O(n log(n)) karmaşıklığına sahiptir. Girdi listesini en küçük hale gelene kadar ikili parçalara ayırır ve bu parçaları kendi aralarında sıralayarak birleştirir ve nihayetinde sıralanmış çıktı elde edilir.

Wikipedia

Elimizde böyle bir liste olsun ve bu listeyi sıralamaya çalışıyor olalım.

  | 38 | 27 | 43 | 3 | 9 | 82 | 10 | 

İlk açamada listemizi 2'ye bölüyoruz. Tabi burada listemizdeki eleman sayısı tek olduğundan tam olarak bölemiyoruz.

                                                           | 38 | 27 | 43 | 3 |            | 9 | 82 | 10 | 

İşlemimizi karşılaştırabileceğimiz 2 sayı kalana kadar devam ettiriyoruz.

                                                      | 38 | 27 |         | 43 | 3 |         | 9 | 82 |        | 10 |  

Evet şimdi sayılarımızı sıralayarak birleştirebiliriz. 

                                                      | 27 | 38 |          | 3 | 43 |        | 9 | 82 |        | 10 | 

                                                          | 3 | 27 | 38 | 43 |               | 9 | 10 | 82 | 

                                                                      | 3 | 9 | 10 | 27 | 38 | 43 | 82 |

Mantığını anladığımıza göre java ile nasıl kodlayabileceğimize bakabiliriz.

Burada sort, doSort ve merge adında 3 fonksiyon mevcut. doSort recursive olarak çalışıyor. Main fonksiyonunda sort fonksiyonuna parametre olarak gönderilen dizinin boyutunda boş bir dizi oluşturuluyor(tmp). Sonrasın da parametler doSort fonksiyonuna gönderiliyor. Orada bölünen dizi merge fonksiyonunda sıralanarak birleştiriliyor. Kodu satır satır açıklamam epeyce bir zaman alır. Bunun yerine kod parçasını alıp debug etmenizi öneririm. Bir sonraki yazıda görüşmek üzere. İyi çalışmalar.