Bu algoritmanın en iyi, ortalama, ve en kötü çalışma performansı şöyledir:
Best Average Worst
Ω(n.log(n)) θ(n.log(n)) O(n.log(n))
Best Average Worst
Ω(n.log(n)) θ(n.log(n)) O(n.log(n))
Aşağıdaki resme bakalım.Elimizde 7 tane sayı var ve biz bunları küçükten büyüğe sıralamak istiyoruz. Her seferinde elimizdeki listeyi ortadan(2'ye) böleceğiz. Eğer aşağıda olduğu gibi listedeki eleman sayısı tek ise listeyi ilk parça ikinci parçadan bir fazla olacak şekilde böleceğiz.Aşağıda 7 tane sayı var. Dolayısıyla sırasıyla 4 ve 3 elemanlı listelere böldük. Tüm liste elemanları tek tek ayrılana kadar bu listeyi ortadan bölmeye devam ettik.
Bu adımdan sonra merge etmeye yani birleştirmeye başladık.Önce küçük sonra büyük gelecek şekilde tüm parçaları birleştirmeye başladık.Aşağıdaki aşamadan itibaren daha detaylı açıklayarak devam edelim.
a b c d
27 38 3 43 9 82 10 Bunları merge edeceğiz(birleştireceğiz).
a ve b'yi merge edeceğiz sonra c ve d'yi merge edeceğiz.
a ve b'yi şöyle merge ederiz:
a ve b'nin ilk elemanlarına bakarız. 3 <27 olduğu için 3 ü başa yazdık. a ve b aşağıdaki kaldı.
a b
27 38 42 a'nın ve b'nin ilk elemanlarına baktık. 27 < 42 olduğu için 27'i alıp 3 ün yanına yazdık. a ve b aşağıdaki gibi kaldı.
a b
38 42 a'nın ve b'nin ilk elemanlarına baktık. 38 < 42 olduğu için 38'i alıp 27'nin yanına yazdık.
Kalan 42'yi de sona yazdık.
c ve d de benzer şekilde merge edilir.
Son merging step'de 3 27 38 43 ile 9 10 82 merge edilcek.Her ikisinin de ilk elemanlarına bakılır ve küçük olan yazılır:
3 27 38 43 ile 9 10 82 3 < 9 -> 3
27 38 43 ile 9 10 82 9 < 27 -> 3 9
27 38 43 ile 10 82 10 < 27 -> 3 9 10
27 38 43 ile 82 27 < 82 -> 3 9 10 27
38 43 ile 82 38 < 82 -> 3 9 10 27 38
43 ile 82 43 < 82 -> 3 9 10 27 38 43
82 -> 3 9 10 27 38 43 82
Aynı işlemi aşağıdaki gif resmi ile de izleyebilirsiniz.
Bu yazımda kullandığım görsel kaynaklar : Wikipedia.
Hiç yorum yok:
Yorum Gönder