Toshkent axborot texnologiyalari universiteti samarqand filiali mustaqil ish

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;