Toshkent axborot texnologiyalari universiteti samarqand filiali mustaqil ish

private static void merge(int[] array, int[] left, int[] right) {

int leftIndex = 0; //left va right submassiv elementlarini

int rightIndex = 0; //to`g`ri saralangan tartibda

int targetIndex = 0; //array massiviga joylashtirsh

int remaining = left.length+right.length;

while(remaining>0){

if (leftIndex >= left.length){

array[targetIndex] = right[rightIndex++];

}else

if (rightIndex >= right.length){

array[targetIndex] = left[leftIndex++];

}else

if (left[leftIndex]-right[rightIndex] < 0){

array[targetIndex] = left[leftIndex++];

}else{

array[targetIndex] = right[rightIndex++];

}

targetIndex++;

remaining--;

}

}

}

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:

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.