Merge Sort (Birləşdirərək Sıralama) alqoritmi

[codex]

Merge Sort — çox effektiv və müqayisəyə əsaslanan sıralama alqoritmidir. Bu alqoritm sıralanmamış massivləri iki yerə bölərək rekursiv şəkildə sıralayır və daha sonra bu sıralanmış hissələri birləşdirərək tək bir sıralanmış massiv yaradır. Bu proses massiv tamamilə sıralanana qədər davam edir.

Merge Sort-un zaman mürəkkəbliyi O(n log n) təşkil edir ki, bu da onu böyük verilənlər üzərində işləmək üçün uyğun edir. Eyni zamanda stabil alqoritm hesab olunur, yəni sıralama zamanı eyni dəyərə sahib elementlərin əvvəlki ardıcıllığı qorunur.

---

️ Merge Sort-un implementasiyası

İki massivin birləşdirilməsi funksiyası

İlk addım olaraq sıralanmış iki massiv birləşdirilir. Bu mərhələ, Merge Sort funksiyasının əsas tərkib hissəsidir.

1. Boş bir nəticə massivi yaradılır, hər iki massivin başlanğıcındakı ən kiçik dəyərlərə baxılır;
2. Massivlərdə hələ də baxılmamış dəyərlər olduqca:
   • Əgər birinci massivdəki dəyər ikincidəkindən kiçikdirsə, bu dəyər nəticə massivinə əlavə edilir və birinci massivdə növbəti dəyərə keçilir;
   • Əgər ikinci massivdəki dəyər birincidən kiçikdirsə, həmin dəyər əlavə olunur və ikinci massivdə növbəti dəyərə keçilir;
   • Əgər hansısa massiv bitibsə, digərindəki bütün dəyərlər əlavə olunur.

Kod nümunəsi:

const mergeArrays = (arr1: number[], arr2: number[]): number[] => {
  const result: number[] = [];
  let i = 0, j = 0;

  while (i < arr1.length || j < arr2.length) {
    if (arr2[j] === undefined || arr1[i] < arr2[j]) {
      result.push(arr1[i++]);
    } else {
      result.push(arr2[j++]);
    }
  }

  return result;
}

---

🧠 Merge Sort alqoritminin özünü

1. Əgər massivdə 1 və ya 0 element varsa, o artıq sıralanmış sayılır və olduğu kimi qaytarılır;
2. Massiv ortadan ikiyə bölünür. Bunun üçün mid dəyişəni yaradılır və Math.floor(array.length / 2) ilə təyin olunur;
3. Sonra left və right adlı iki massiv yaradılır. Bunlar slice() funksiyası ilə massivdən ayrılır:
   • left → array.slice(0, mid)
   • right → array.slice(mid)
4. left və right massivləri mergeSort funksiyası ilə rekursiv şəkildə sıralanır;
5. Sonda mergeArrays(left, right) funksiyası ilə sıralanmış hissələr birləşdirilir və nəticə olaraq geri qaytarılır.

Kod nümunəsi:

const mergeSort = (array: number[]): number[] => {
  if (array.length <= 1) return array;

  const mid = Math.floor(array.length / 2);
  const left = mergeSort(array.slice(0, mid));
  const right = mergeSort(array.slice(mid));

  return mergeArrays(left, right);
}

---

Nəticə

Merge Sort — həm sabit, həm də optimal zaman mürəkkəbliyinə malik olan güclü sıralama alqoritmidir. Onun əsas üstünlükləri:

• Böyük verilənlər üçün uyğundur;
• Eyni elementlərin sırasını qoruyur (stabil sıralama);
• Rekursiv yanaşma və “böl və fəth et” paradiqminə əsaslanır;
• O(n log n) performansı ilə çox effektivdir.

---

Merge Sort-u vizual olaraq görmək üçün Transilvaniya-sakson (alman) xalq rəqsinə tamaşa etməniz kifayət edəcək