Ajrat va hukmronlik qil

Misollar
Merge Sort algoritmi va uning ishlash prinsipi.
"Ajrat va hukmronlik qil" usulining eng mashhur saralash algoritmlaridan biri Merge Sort (Birlashtirib saralash)dir. Merge Sort algoritmi bu saralanmagan massivni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash printsipida to'liq ajrat va hukmronlik qil g'oyasini uchratish mumkin.
Demak, merge sort algoritmi asosiy ikkita qismdan iborat:

1. 
   Berilgan massivni rekursiv holda teng ikkita qismlarga bo'lib chiqish. Bu qadam, qism massivlar uzunligi 1 ga (yoki undan kichik) teng bo'lib qolguncha davom etadi.
   
2. 
   Hosil bo'lgan massivlarni qaytib birlashtirib chiqish va bir vaqtning o'zida hosil bo'luvchi massiv saralangan bo'lishini ta'minlash.
   

Merge sort algoritmi qanday ishlashini vizual tasavvur qilish uchun quyidagi rasmga e'tibor bering. Unda amallar tartibi ham ko'rsatib qo'yilgan

Merge sort algoritmining ishlash printsipi.
Ko'rib turganingizdek algoritm ishlash prinsipini tushunish uchun unchalik ham murakkab emas. Va yana e'tibor bergan bo'lsangiz, birinchi bo'linishdan keyingi massivning chap va o'ng qismlarida asosiy massiv bilan bir xil amal ketmoqda, ya'ni bizning masalamizning qism masalasi ham bosh masala bilan bir xilda ishlaydi.
Merge sort algoritmi qadamlari:
1. Merge Sort funksiyasiga massiv va uning boshlang'ich (left) va oxirgi nuqtalari (right) beriladi.
2. Massivning o'rtasi hisoblanadi: mid = (left + right)/2. Bu uni teng ikkiga bo'lish uchun kerak bo'ladi.
3. Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.
4. 2- va 3-qismlarda hosil bo'lgan massivlar birlashtirib chiqiladi. (Massiv mavzusidagi ikkita massivni birlashtirish masalasini ko'rib chiqing).