Birlashmali saralash (Merge Sort)

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:

1. Massivni guruhlarga rekursiv ajratish amali (
   sort).
2. To`g`ri tartibda birlashtirish amali (merge).

Java dasturlash tilidagi algoritm kodi:

import java.util.Arrays;
public class MergeSort {
    public static void main(String[] args) {
        int[] A = {6,5,12,10,9,1};
        sort(A); //saralashni boshlash
        System.out.println(Arrays.toString(A)); //natijani chop qilish
    }
    private static void sort(int[] array) {
        if(array.length0){                               
            if (leftIndex >= left.length){
                array[targetIndex] = right[rightIndex++];
            }else 
                if (rightIndex >= right.length){
                    array[targetIndex] = left[leftIndex++];
                }else 
                    if (left[leftIndex]-right[rightIndex] 

	Qadamlarda tasvirlanishi:

	

	Aytib o`tish joizki, chiziqli saralash algoritmlaridan farqli o`laroq, 
	birlashmali saralash massiv avvaldan saralangan yoki saralanmaganligiga qaramay ajratib birlashtiradi. Shuning uchun ham eng yomon holatda, u chiziqli saralash algoritmlariga qaraganda tez ishlashiga qaramay, eng yaxshi holatda uning samarasi chiziqli algoritmlardan past bo`ladi. Demak, birlashmali saralashni qisman saralangan massivlarni saralash uchun qo`llamagan ma'qul.
	


	Birlashmali saralashning boshqa saralash algoritmlari bilan solishtirish:
	
	
	

Jadvaldan ko`rinib turibdiki, umumiy holatda birlashmali saralash algoritmidan foydalanish samaraliroq hisoblanadi.