4-§ Birlashtirib saralash algoritmlari Merge sort algoritmi. Birlashtirib saralash (Merge sort)

Birlashtirish bosqichi. Birlashtirish bosqichi asosiy pogʻonaga 
yetib borganida va biz A [p..r] massivi uchun ikkita tartiblangan A [p..q] 
va A [q + 1, r] kichik massivlarni olsak, natijalarni A [p..r] massiviga 
birlashtiramiz. Bu ikkita tartiblangan A [p..q] va A [q + 1, r] 
massivlarning birlashmasidir (12-rasm). 
Birlashtirib saralash algoritmi. MergeSort funksiyasi massivni 
ketma-ket ikki qismga ajratadi, biz 1-darajali ichki massivda MergeSort-
ga oʻtishga harakat qiladigan bosqichga yetguncha ya‘ni p == r 
boʻlguncha. 
Shundan soʻng, birlashtirish funksiyasi ishga tushadi, bu 
tartiblangan massivlarni butun massiv birlashguncha katta massivlarga 
birlashtiradi. 
12-rasm. Merge Sort algoritmining ishlash prinsipi 

---

65 
1. MergeSort(A, p, r) 
2. If p > r
3. return; 
4. q = (p+r)/2; 
5. mergeSort(A, p, q) 
6. mergeSort(A, q+1, r) 
7. merge(A, p, q, r) 
Butun massivni saralash uchun MergeSort (A, 0, length (A) -1) ga 
murojaat qilishimiz kerak. 
13-rasmda koʻrsatilgandek, birlashtirib saralash algoritmi 1 
elementli massivning asosiy holatiga kelgunimizcha massivni rekursiv 
ravishda ikkiga boʻladi. Soʻngra birlashtirish funksiyasi saralangan ichki 
massivlarni tanlaydi va butun qatorni asta-sekin saralash uchun ularni 
birlashtiradi. 
13-rasm. Merge Sort algoritmida massivni qismlarga boʻlish 
jarayoni 

---

66 
Algoritmning eng muhim qismi bu "birlashtirish" bosqichidir. 
Birlashish bosqichi - ikkita katta roʻyxat (massiv) yaratish uchun ikkita 
tartiblangan roʻyxatni (massivlarni) birlashtirish boʻyicha oddiy 
muammoning yechimi. 
Ikkinchi massivda boshqa elementlar qolmaganligi va ikkala 
massiv ham ishga tushirilganda saralanganligini bilganimiz uchun 
qolgan massivlarni toʻgʻridan-toʻgʻri birinchi massivdan nusxalashimiz 
mumkin.