Ajrat va xukmronlik qil

Birlashtirish orqali (MergeSort) saralash.
 
 MergeSort O(NlogN) da ishlaydigan optimal saralash algoritmlaridan biri. Eng yaxshi 
holatda ham, eng yomon holatda ham O(NLogN) assimptotikada ishlaydi. Hamda, u barqaror 
saralaydi, ya’ni sonlar ketma-ketligini buzmagan holda. Masalan, sonlardan tashqari, ularning 
kalit sonlari bo‘lsa, kalit soni 3 bo‘lgan 2 soni kalit soni 5 bo‘lgan 2 sonidan oldin kelsa, 
MergeSortda saralangandan so‘ng ham kalit soni 3 bo‘lgan 2 soni oldin keladi. QuickSort da 
doim ham bu shart bajarilavermaydi. 
Algoritmning ishlash prinsipi quyidagicha: Massivni teng ikkiga bo‘lamiz. O‘ng tomonni 
alohida saralaymiz, chap tomonni alohida. So‘ng ikki saralangan qismni O(n) ya’ni n ta 
operatsiyada qo‘shib, to‘liq saralangan massiv olamiz. Aynan shu operatsiya, ya’ni qo‘shish - 
Merge ning hisobiga algoritm shunday nom olgan. Endi chap va o‘ng tomonlarini saralash 
uchun ham, ularni ikkiga bo‘lib xudi shu ishni bajaramiz va hk. Massivni bo‘lishni to unda 2 ta 
element qolguncha davom ettiramiz. 
Faraz qilaylik, bizda Merge(a: Array of Integer, Left, Mid, Right: Integer) funksiyasi 
bo‘lsin. YA’ni, a massivning L -Mid qismi saralangan, Mid + 1 - R qismi saralangan. Shu 
qismlarni qo‘shib, L –R kesmada saralangan qilish. Bunda Mid L va R kesma o‘rtasi. 
7.2-rasm. 
7.3-rasm. 

---

7.4-rasm. 
7.5-rasm. 
7.6-rasm. 
7.7-rasm. 
7.8-rasm 
7.9-rasm. 
7.10-rasm.
7.11-rasm. 
[L, R] oraliq m=(L+R) / 2 o‘rtasi orqali ikkita [L, m] va [m+1, R] oraliqqa ajratiladi va ular 
alohida saralanadi. 

---

7.13-rasm. 
Shunday Merge funksiya asosida MergeSortni quyidagicha yozish mumkin. 
#include 
using namespace std; 
int helper[1000001]; 
void Merge(int a[],int left,int middle,int right){ 
for(int i=left,j=middle,k=left;kif(i==middle){ helper[k]=a[j++];continue;} 
if(j==right ){ helper[k]=a[i++];continue;} 
helper[k]=( a[i]< a[j])?a[i++]: a[j++]; 
} 
for(int k=left;k} 
void MergeSort(int a[],int left,int right){ 
if(right-left==1)return; 
int middle=(left+right)>>1; 
MergeSort(a,left,middle); 
MergeSort(a,middle,right); 
Merge(a,left,middle,right); 
} 
int main(){ 
int a[10000], n , i; 
cin>>n; 
for(i=0;i>a[i]; 
MergeSort(a,0,n); 
for(i=0;ireturn 0; 
}
 
Amaliy ish topshiriqlari va
ish davomida ishlab chiqiladigan dasturning to‘liq namunasi.