Muhammad al-xorazmiy nomidagi toshkеnt axborot tеxnologiyalari univеrsitеti qarshi filiali “ kompyuter injiniringi ” fakultеti

Qo’shilib saralash
4.
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.
Birlashmali saralashning boshqa saralash algoritmlari bilan solishtirish:
Algoritm
Eng yaxshi
O`rtacha
Eng yomon
Tanlab saralash
O(n^2)
O(n^2)
O(n^2)
Pufakchali saralash
O(n)
O(n^2)
O(n^2)
Tezkor saralash
O(n log(n))
O(n log(n))
O(n^2)
Birlashmali saralash
O(n log(n))
O(n log(n))
O(n log(n))
Jadvaldan ko`rinib turibdiki, umumiy holatda birlashmali saralash 
algoritmidan foydalanish samaraliroq hisoblanadi.
• 
#include
• 
#include
• 
#include
• 
using namespace std;
• 
int a[100000], b[100000];
•