O’zbekiston respublikasi oliy va o’rta maxsus talim vazirligi

Piramidali saralash  

 

Algaritm murakkabligi O(N*logN)  

 

Birlashmali saralash (Merge Sort)  

Bu algoritm Jon Fon Neyman tamonidan 1946 yilda taklif qilingan. 

 

 

Jon Fon Neyman Vengriyalik matematika, kvant fizikasi, funksional analiz,to’plamlar 

nazariyasi, ekonomika, informatika kabi fanlarga munosib hissa qo’shgan.  

 

 

 

 

---

 

 

Birlashmali saralash (Merge Sort) algoritmi asosiy beshta saralash algoritmlari (pufakchali 

saralash, tezkor saralash va boshqalar) dan biri bo`lib, chiziqli saralash algoritmlaridan farqli 

ravishda "bo`lib tashla va hukmronlik qil" tipidagi algoritm hisoblanadi.  

Bu tipdagi algoritmlar katta hajmdagi masalalarni nisbatan kichik bo`lgan va oson yechiladigan 

qismlarga ajratgan holda bajaradi. Bunday algoritmlar masalalarni hal qilishda vaqtdan katta 

yutuq qilish imkonini beradi. 

Birlashmali saralashda biz berilgan massivni uzunligi faqat 1 elementga teng bo`lgan qismlar 

qolmaguncha o`rtasidan ajratamiz. Keyin bu qismlar to`g`ri tartibda birlashtiriladi.  

Keling ushbu massivni qaraylik: 

 

 

 

Uni teng ikkiga ajratamiz: 

 

 

 

Va yana har bir qismni ikkiga ajratamiz, toki 1 elementli qismlar qolmagunicha: 

 

 

 

---

Massivni maksimal qisqa qismlarga ajratgandan so`ng, ularni to`g`ri tartibda birlashtiramiz, 

ya'ni: 

 

 

 

Dastlab, 2 elementli saralangan guruhlarni olamiz va ularni 4 elementli guruhlarga birlashtiramiz 

va yakunida hammasini birlashtirgan holda saralangan massivni hosil qilamiz. 

 

 

 

Algoritm ishlashi uchun quyidagi amallarni amalga oshirish kerak: 

Massivni guruhlarga rekursiv ajratish amali ( sort).  

To`g`ri tartibda birlashtirish amali (merge).