Ma’lumotlar tuzilmasi va algoritmi

Merge sort algoritmi qadamlari

1. 
   Merge Sort funksiyasiga array va uning boshlang’ich (left) va oxirgi nuqtalari (right) beriladi.
   
2. 
   Arraynining o’rtasi hisoblanadi: mid = (left + right)/2. Bu narsa 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 arraylar birlashtirib chiqiladi. (Array mavzusidagi ikkita arrayni birlashtirish masalasini ko’rib chiqing)
   

Algoritm ishlash tezligi O(nlogn) bo’lib tezligi O(n²) bo’lgan oddiy Bubble, Insertion, Selection Sortlardan ancha tez ishlaydi. O’zi umuman olganda, taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(nlogn) bo’lishi isbotlangan.
Merge sort turg’un saralash hisoblanadi, ya’ni saralamagan arrayda bir nechta bir xil elementlar kelgan bo’lsa, ularning tartibi saralangan massivda ham o’zgarib ketib qolmaydi.
Algoritm ishlashi uchun xotiradan qo’shimcha O(n) joy talab qiladi.
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.length<=1){ //massiv qismlarini elementlar sonin aniqlash
return; //1 dan kichik yoki teng bo`lsa ajratishni to`xtatish
}
int leftSize = array.length/2; //chap tomon bo`lak uzunligini aniqlash
int rightSize = array.length-leftSize; //o`ng tomon bo`lak uzunligini aniqlash