Merge sort: bo'lib, saralab, birlashtirish — har doim O(n log n)

Qisqacha: Merge sort massivni ikkiga bo'ladi, har yarmini o'zi bilan saralaydi va ikki saralangan yarimni bitta ro'yxatga birlashtiradi (merge). Bo'lish log₂ n qatlam beradi, har qatlamda birlashtirish n ish qiladi — jami O(n log n), eng yomon holatda ham. Narxi — O(n) qo'shimcha xotira. Teng elementlar tartibini saqlaydi (barqaror).

Bu darsda

• Ikki saralangan ro'yxatni bitta o'tishda birlashtiradigan merge funksiyasini yoza olasiz.
• Merge sort'ni rekursiv yozib, uning ishini daraxt ko'rinishida kuzatasiz.
• Nega vaqt doim O(n log n), xotira esa O(n) ekanini hisoblab, o'lchov bilan tasdiqlaysiz.
• Barqarorlik <= belgisiga bog'liqligini ko'rasiz va bog'langan ro'yxatni ham saralay olasiz.

Oldin bilishingiz kerak: Bo'lib-yech (divide and conquer), Oddiy saralashlar, Rekursiv fikrlash, Linked list.

1. Nega bu kerak?

O'tgan darsda insertion sort'ni yozdik. U kichik va deyarli tartiblangan ro'yxatda juda yaxshi. Lekin «Bahor»da oy oxirida hisob-kitob bor: bir oyda 80 000 ta buyurtma yig'ildi. Jasur aka ularni summa bo'yicha saralangan holda ko'rmoqchi.

Sardor insertion sort'ni ishga tushirdi va dastur bir necha soniya "o'ylab qoldi". Sababi ma'lum: insertion sort O(n²). Buyurtmalar ikki baravar ko'paysa, kutish to'rt baravar uzayadi.

Shu payt Jasur aka boshqa narsani esladi. "Kechqurun zal kassasi va yetkazish kassasi menga ikki varaq beradi. Ikkalasi ham summa bo'yicha tartiblangan. Men ularni bitta ro'yxatga juda tez qo'shaman: ikki varaqning tepasiga qarayman, kichigini yozaman, yana tepasiga qarayman..."

Bugungi darsning hammasi shu kuzatuvdan chiqadi. Ikki saralangan ro'yxatni qo'shish arzon. Demak, saralanmagan ro'yxatni yarimlarga bo'lib, har yarmini saralab, keyin qo'shsak bo'ladi. Bu — merge sort (birlashtirib saralash).

2. Birlashtirish: ikki varaqning tepasiga qarash

2.1 G'oya

Ikki saralangan ro'yxat bor: chap [5, 28, 30, 35] va o'ng [8, 12, 20, 40] (ming so'mda). Har birining eng kichigi — boshida. Demak, umumiy eng kichik element ikki boshdan biri. Uni olamiz va shu ro'yxatda bitta oldinga suramiz. Keyin yana ikki boshni solishtiramiz.

Bo'lib-yech darsida bu birlashtirishni qisqacha ko'rgan edik — endi uni har tomonlama ochamiz. Buni ikki ko'rsatkich bilan qilamiz (Ikki ko'rsatkich darsidagidek): i — chapdagi navbatdagi element, j — o'ngdagi. Kuzating:

Har qadamda bitta solishtirish va bitta element natijaga ketdi. Chap ro'yxat tugagach, o'ngda faqat 40 qoldi. U allaqachon saralangan va hammasidan katta — solishtirmasdan oxiriga qo'shamiz.

2.2 Kod

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  // bittasi tugadi — ikkinchisining qolgani o'z-o'zidan tartibda
  return [...result, ...left.slice(i), ...right.slice(j)];
}

console.log(merge([5, 28, 30, 35], [8, 12, 20, 40]));
console.log(merge([], [5, 8])); // [ 5, 8 ]
console.log(merge([28, 35], [28])); // [ 28, 28, 35 ]

Konsolda:

[
   5,  8, 12, 20,
  28, 30, 35, 40
]
[ 5, 8 ]
[ 28, 28, 35 ]

Node 6 tadan uzun sonli massivni ustunlarga bo'lib chiqaradi — qiymatlar o'sha-o'sha. Kodni qatorma-qator ko'ramiz:

• left[i++] — avval left[i] olinadi, keyin i bittaga oshadi. i++ ning bu xususiyatini arifmetik operatorlar darsida ko'rgansiz.
• Sikl shartida && bor: ikkala ro'yxatda ham element qolgan paytda solishtiramiz.
• left.slice(i) — chap ro'yxatning i dan keyingi qolgani. Ikkalasidan bittasi doim bo'sh bo'ladi.

2.3 Birlashtirish narxi

Chapda a ta, o'ngda b ta element bo'lsa, natijaga jami a + b ta element tushadi. Har biri bir marta ko'chiriladi. Solishtirishlar esa a + b - 1 tadan oshmaydi. Demak, birlashtirish O(a + b) — chiziqli. Xotira ham O(a + b): result yangi massiv.

Tekshirib ko'ring: merge([1, 2, 3], [10, 20, 30]) nechta solishtirish qiladi? merge([10, 20, 30], [1, 2, 3]) chi?

3. Merge sort: bo'l, saralash, birlashtir

3.1 Rekursiv g'oya

Endi saralanmagan ro'yxatni olamiz. Bo'lib-yech darsidagi uch qadam:

1. Bo'lish: massivni o'rtadan ikkiga bo'lamiz.
2. Yechish: har yarmini merge sort bilan saralaymiz (rekursiya).
3. Birlashtirish: ikki saralangan yarimni merge bilan qo'shamiz.

To'xtash sharti (asos holat): bitta yoki nol elementli ro'yxat allaqachon saralangan. Ikkinchi qadamda "ishonch sakrashi" (Rekursiv fikrlash) kerak bo'ladi: funksiya yarimni saralay oladi deb ishonamiz va faqat birlashtirishni o'ylaymiz.

3.2 Daraxtda kuzatamiz

Har tugun — bitta mergeSort chaqiruvi. Pastga qarab ro'yxat bo'linadi. Yuqoriga qaytishda tugun matni saralangan holatga almashadi:

Daraxtning uch qatlami bor: 8 → 4 → 2 → 1. Bu log₂ 8 = 3. Birlashtirish pastdan yuqoriga ketdi: avval juftlar, keyin to'rtliklar, oxirida hammasi.

3.3 Kod

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr; // asos holat
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid)); // chap yarim
  const right = mergeSort(arr.slice(mid)); // o'ng yarim
  return merge(left, right);
}

const orders = [35000, 28000, 5000, 30000, 12000];
const sorted = mergeSort(orders);
console.log(sorted); // [ 5000, 12000, 28000, 30000, 35000 ]
console.log(orders); // [ 35000, 28000, 5000, 30000, 12000 ]

Ikkinchi console.log ga qarang: asl orders o'zgarmadi. slice nusxa oladi, merge yangi massiv qaytaradi. Bu variant toSorted kabi ishlaydi (nusxa bilan o'zgartirish).

Tekshirib ko'ring: mergeSort([7]) nima qaytaradi va nechta merge chaqiriladi?

4. Murakkablik: nega doim n log n

4.1 Vaqt

Kodning murakkabligini hisoblash darsidagi daraxt usulini qo'llaymiz:

• Qatlamlar soni. Har qatlamda bo'lak ikki baravar kichrayadi. n ta element bittaga tushguncha log₂ n qatlam.
• Har qatlamdagi ish. Bir qatlamdagi hamma bo'laklarning uzunliklari yig'indisi — n. Har bo'lakni birlashtirish uzunligiga teng ish qiladi. Demak, qatlamda jami O(n).
• Jami: log₂ n qatlam × n = O(n log n).

Muhimi: bu hisobda kirish ma'lumotining tartibi umuman qatnashmadi. Ro'yxat saralangan bo'lsin, teskari bo'lsin, aralash bo'lsin — bo'lish bir xil. Solishtirishlarni sanab tekshiramiz. Urug'li generator o'tgan darslardagidek:

let comparisons = 0;

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    comparisons++;
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  return merge(left, mergeSort(arr.slice(mid)));
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}

const n = 1024;
const random = makeRandom(2026);
const inputs = {
  saralangan: Array.from({ length: n }, (_, i) => i),
  teskari: Array.from({ length: n }, (_, i) => n - i),
  tasodifiy: Array.from({ length: n }, random),
};
for (const [name, arr] of Object.entries(inputs)) {
  comparisons = 0;
  mergeSort(arr);
  console.log(`${name}: ${comparisons} ta`);
}
console.log(`n·log₂n = ${n * Math.log2(n)}`);

Konsolda:

saralangan: 5120 ta
teskari: 5120 ta
tasodifiy: 8940 ta
n·log₂n = 10240

Saralangan va teskari ro'yxatda har merge bitta yarimni to'liq "yutib" yuboradi — solishtirish ikki baravar kam. Lekin bu faqat o'zgarmas ko'paytuvchi: n log n ning yarmi. Eng yomon holatda ham n · log₂ n dan oshmaydi. Insertion sort esa saralangan ro'yxatda 1 023 ta, teskarida esa 523 776 ta solishtirish qilgan bo'lardi.

Ko'ryapsizmi: saralangan ro'yxatda insertion sort yutadi. Merge sort esa kafolat beradi — hech qachon n log n dan sekin emas.

4.2 Xotira

Merge sort'ning narxi — xotira. Har merge yangi massiv yaratadi. Bir paytda tirik turgan qo'shimcha xotira — taxminan n ta element (eng tepadagi birlashtirish natijasi) va yo'ldagi slice nusxalari. Bundan tashqari, rekursiya stekida log₂ n ta chaqiruv turadi. Jami O(n) qo'shimcha xotira (Xotira murakkabligi).

Bizning variantimiz har qatlamda slice bilan yangi nusxa ham oladi, shuning uchun axlat yig'uvchiga (GC) ish ko'p. Professional variantlar bitta yordamchi massivni oldindan yaratib, hamma birlashtirishlarda qayta ishlatadi — Big-O o'zgarmaydi, lekin o'zgarmas ko'paytuvchi kichrayadi.

5. O'lchov: n ikki baravar oshsa

Benchmarking darsidagi usul bilan o'lchadik: tasodifiy sonlar (urug' 2026), har n alohida jarayonda, 3 isitish va 7 o'lchov medianasi. Kirish o'lchovdan oldin yasaladi — vaqtga faqat saralash kiradi:

const arr = randInts(n); // urug'li kirish — o'lchanmaydi
const start = performance.now();
mergeSort(arr); // faqat shu o'lchanadi
const ms = performance.now() - start;

Insertion sort'ni shu hajmda o'lchab bo'lmaydi — juda sekin. Uni kichikroq n da o'lchadik: 10 000 son — ≈ 21 ms, 20 000 — ≈ 87 ms (×4,1), 40 000 — ≈ 350 ms (×4,0), 80 000 — ≈ 1,4 s (×4,1). Merge sort 80 000 sonni taxminan 30 ms da saralaydi — qariyb 50 baravar tez.

Merge sort ustunida har qatorda vaqt taxminan ikki baravar oshdi (×1,9 dan ×2,1 gacha). n log n aynan shuni kutadi: n ikki baravar, log n esa biroz oshadi. Insertion sort'da esa vaqt har safar to'rt baravar oshdi — n² ning belgisi.

Nimaga qarang: bizning oddiy mergeSort V8 ning ichki toSorted i bilan deyarli teng chiqdi — ikkalasi ham n log n. Insertion sort chizig'i esa tepaga uchib ketdi. Aniq millisekundlar sizning kompyuteringizda boshqacha bo'ladi — nisbatga qarang.

6. Barqarorlik: <= va < farqi

6.1 Teng summali buyurtmalar

Buyurtmalar kelish vaqti bo'yicha yozilgan. Jasur aka ularni summa bo'yicha saralamoqchi, lekin teng summalilar kelish tartibida qolsin. Bu — barqaror saralash (stable sort), uni sort va taqqoslash funksiyasi darsida ko'rgansiz. Merge sort barqarormi?

function mergeBy(left, right, key) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i][key] <= right[j][key]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

function mergeSortBy(arr, key) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSortBy(arr.slice(0, mid), key);
  const right = mergeSortBy(arr.slice(mid), key);
  return mergeBy(left, right, key);
}

// buyurtmalar kelish tartibida (vaqt bo'yicha)
const orders = [
  { time: "12:05", sum: 35000 },
  { time: "12:10", sum: 28000 },
  { time: "12:15", sum: 35000 },
  { time: "12:20", sum: 5000 },
  { time: "12:25", sum: 28000 },
];
for (const o of mergeSortBy(orders, "sum")) {
  console.log(o.sum, o.time);
}

Konsolda:

5000 12:20
28000 12:10
28000 12:25
35000 12:05
35000 12:15

Ikki 28 000 lik buyurtma 12:10 va 12:25 tartibida qoldi. Ikki 35 000 lik ham. Merge sort barqaror.

6.2 Barqarorlik qayerdan keladi

Gap bitta belgida: left[i][key] <= right[j][key]. Qiymatlar teng bo'lsa, chapdagisi olinadi. Chap yarim esa asl ro'yxatda oldinroq turgan elementlardan iborat. Shuning uchun teng elementlar orasida avvalgisi avval qoladi.

Agar < yozsangiz, teng holatda o'ngdagisi olinadi va tartib buziladi: natijada 28000 12:25 birinchi chiqadi. Kod xatosiz ishlaydi, saralash ham to'g'ri ko'rinadi — faqat barqarorlik jimgina yo'qoladi. Buni Saralash tushunchalari darsida ko'rgan ko'p kalitli saralash payqaydi.

7. Bog'langan ro'yxatni saralash

Merge sort'ning yana bir kuchli tomoni bor: u elementlarga ketma-ket murojaat qiladi. Indeks bilan sakrash kerak emas. Shuning uchun bog'langan ro'yxat uchun eng qulay saralash — merge sort.

Tugunlar — Linked list darsidagi ListNode shaklidagi oddiy obyektlar (value va next). Massivda arr[mid] darhol topiladi. Bog'langan ro'yxatda o'rtani topish uchun tez/sekin ko'rsatkich usulini qo'llaymiz: tez ko'rsatkich ikki qadam, sekini bir qadam yuradi. Tez oxiriga yetganda sekini o'rtada turadi.

// har tugun — { value, next }: ListNode bilan bir xil shakl
function fromArray(values) {
  let head = null;
  for (let k = values.length - 1; k >= 0; k--) {
    head = { value: values[k], next: head };
  }
  return head;
}

function toArray(head) {
  const values = [];
  for (let n = head; n; n = n.next) values.push(n.value);
  return values;
}

function mergeLists(a, b) {
  const dummy = { next: null }; // soxta bosh — kodni soddalashtiradi
  let tail = dummy;
  while (a && b) {
    if (a.value <= b.value) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b; // qolgan qism — butunligicha
  return dummy.next;
}

function sortList(head) {
  if (!head || !head.next) return head;
  // tez/sekin ko'rsatkich bilan o'rtani topamiz
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const second = slow.next;
  slow.next = null; // ro'yxatni ikkiga uzamiz
  return mergeLists(sortList(head), sortList(second));
}

const queue = fromArray([30, 5, 28, 35, 12]);
console.log(toArray(sortList(queue))); // [ 5, 12, 28, 30, 35 ]

Farqga qarang: mergeLists yangi massiv yaratmaydi. U mavjud tugunlarning next havolalarini qayta ulaydi. Shuning uchun bog'langan ro'yxatda merge sort'ning qo'shimcha xotirasi faqat rekursiya steki — O(log n). Vaqt esa baribir O(n log n).

dummy — Linked list masalalari darsidagi soxta bosh (dummy head): natijaning boshini alohida tekshirmaslik uchun qo'yilgan bo'sh tugun. Oxirida dummy.next — haqiqiy bosh.

Tekshirib ko'ring: Nega fast = head.next bilan boshladik, fast = head emas? Ikki tugunli ro'yxatni qo'lda yurib ko'ring.

8. Rekursiyasiz variant: pastdan yuqoriga

Daraxtni yana bir bor eslang. Pastki qatlamda hamma bo'lak bitta elementdan iborat edi. Keyin juftlar birlashdi, keyin to'rtliklar. Shunday ekan, yuqoridan bo'lib tushish shart emas: to'g'ridan-to'g'ri pastdan boshlasa ham bo'ladi. Bu — pastdan yuqoriga merge sort (bottom-up merge sort).

Jasur aka ham kassa varaqlarini shunday birlashtiradi. Avval varaqlarni juft-juft qo'shadi, keyin juftlarni juft-juft, va bitta varaq qolguncha shunday davom etadi. Har aylanishda nima borligini chiqarib ko'ramiz:

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

function mergeSortBottomUp(arr) {
  let parts = arr.map((x) => [x]); // har element — alohida bo'lak
  while (parts.length > 1) {
    const next = [];
    for (let k = 0; k < parts.length; k += 2) {
      const pair = k + 1 < parts.length;
      next.push(pair ? merge(parts[k], parts[k + 1]) : parts[k]);
    }
    parts = next;
    console.log(parts.map((p) => p.join(" ")).join(" | "));
  }
  return parts[0] ?? [];
}

mergeSortBottomUp([35, 28, 5, 30, 12]);
console.log(mergeSortBottomUp([])); // []

Konsolda:

28 35 | 5 30 | 12
5 28 30 35 | 12
5 12 28 30 35
[]

Uchta aylanish bo'ldi — 5 ni ikkiga bo'lib borsak, uch marta bo'linadi (5 → 3 → 2 → 1). Toq sondagi bo'lak (12) juftsiz qolsa, keyingi aylanishga o'zgarishsiz o'tadi. Bo'sh massivda parts ham bo'sh, sikl aylanmaydi va parts[0] ?? [] bo'sh massiv qaytaradi.

Vaqt o'zgarmadi: aylanishlar log₂ n ta, har aylanishda jami n ish — O(n log n). Lekin rekursiya umuman yo'q, demak stek ham ishlatilmaydi. Katta ma'lumotni diskda saralaydigan dasturlar aynan shu variantdan foydalanadi: bo'laklar fayllarda turadi va juft-juft birlashtiriladi.

Tekshirib ko'ring: 1 000 000 ta elementda pastdan yuqoriga merge sort nechta aylanish qiladi?

9. Chegaraviy holatlar

Oxirgi qatorga e'tibor bering. Rekursiya chuqurligi log₂ n — million elementda ham 20 ga yaqin. Shuning uchun merge sort'da stek to'lib qolishidan qo'rqmasa bo'ladi. Keyingi darsdagi quick sort'da bu masala boshqacha.

10. Ko'p uchraydigan xatolar

10.1 Asos holatda faqat bo'sh massiv

function mergeSort(arr) {
  if (arr.length === 0) return arr; // ❌ 1 ta elementda to'xtamaydi
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  return [...left, ...mergeSort(arr.slice(mid))];
}
mergeSort([35, 28]);

Konsolda:

RangeError: Maximum call stack size exceeded

Tarjimasi: "Chaqiruvlar stekining eng katta hajmi oshib ketdi". Nega? Bitta elementli massivda mid = 0. slice(0, 0) — bo'sh, slice(0) — o'sha bitta element. Funksiya o'zini yana bir elementli massiv bilan chaqiradi va bu cheksiz davom etadi. Tuzatish: arr.length <= 1.

10.2 < yozib barqarorlikni yo'qotish

Xato chiqmaydi, sonlar to'g'ri saralanadi. Faqat teng kalitli obyektlar tartibi aralashadi. Tuzatish: merge da doim <= — teng bo'lsa, chapdagisi oldin.

10.3 shift() bilan birlashtirish

Internetda shunday variant ko'p uchraydi: result.push(left[0] <= right[0] ? left.shift() : right.shift()). Chiroyli, lekin shift massivning hamma elementini bir qadam chapga suradi — O(n) (JS amallarining narxi). Birlashtirish O(n²) ga aylanadi. O'lchovimiz: 25 000 son — ≈ 0,35 s, 50 000 — ≈ 2,1 s (×6), 100 000 — ≈ 10,6 s (×5). Indeksli variant 100 000 sonni ≈ 35 ms da saralaydi — 300 baravar tez. Tuzatish: indeks ko'rsatkichlari (i, j).

10.4 Qolgan elementlarni unutish

while tugagach, bitta ro'yxatda elementlar qoladi. return result deb qo'ysangiz, ular yo'qoladi: merge([5, 28], [8]) → [5, 8]. Tuzatish: oxirida ...left.slice(i), ...right.slice(j).

11. Mashqlar

1-mashq (oson): Qo'lda birlashtiring

merge([12, 30, 40], [5, 28, 35]) ni qog'ozda bajaring. Har qadamda i, j va result ni yozing. Nechta solishtirish bo'ldi? Javobni sonda yozing:

2-mashq (o'rta): Uch kassani birlashtiring

Endi «Bahor»da uchta kassa bor: zal, yetkazish va olib ketish. Har biri summa bo'yicha saralangan ro'yxat beradi. mergeThree(a, b, c) funksiyasini yozing. Ishora: darsdagi merge ni ikki marta ishlating.

console.log(mergeThree([5, 30], [12, 28], [8, 35]));
// [ 5, 8, 12, 28, 30, 35 ]

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

function mergeThree(a, b, c) {
  return merge(merge(a, b), c);
}

console.log(mergeThree([5, 30], [12, 28], [8, 35]));
// [ 5, 8, 12, 28, 30, 35 ]

3-mashq (qiyin): Teskari juftlarni sanang

Sardor reyting ro'yxatini tekshirmoqchi: "Taomlar qanchalik noto'g'ri tartibda?" Buning o'lchovi — teskari juftlar, ya'ni Oddiy saralashlar darsidagi inversiyalar soni: i < j, lekin arr[i] > arr[j] bo'lgan juftlar. [3, 1, 2] da ikkita: (3, 1) va (3, 2).

Sodda yechim — hamma juftlar, O(n²). Merge sort bilan O(n log n) da sanang. Ishora: merge da o'ngdagi b[j] olinsa, u chapda qolgan hamma elementlardan kichik. Ular nechta? a.length - i.

kurs/mashqlar/14/29-merge/merge.test.mjs faylida sortAndCount(arr) ni yozing — u { sorted, count } qaytarsin. Testlar (node:test): bo'sh va bitta element, [3, 1, 2], teng qiymatlar, teskari tartib (100 ta element — 4 950 juft) va sodda yechim bilan solishtirish.

// kurs/mashqlar/14/29-merge/merge.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

// saralaydi va "teskari juftlar" sonini sanaydi
function sortAndCount(arr) {
  if (arr.length <= 1) return { sorted: arr, count: 0 };
  const mid = Math.floor(arr.length / 2);
  const left = sortAndCount(arr.slice(0, mid));
  const right = sortAndCount(arr.slice(mid));
  const a = left.sorted;
  const b = right.sorted;
  const sorted = [];
  let count = left.count + right.count;
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) {
      sorted.push(a[i++]);
    } else {
      count += a.length - i; // b[j] chapda qolganlardan kichik
      sorted.push(b[j++]);
    }
  }
  sorted.push(...a.slice(i), ...b.slice(j));
  return { sorted, count };
}

// sodda yechim — hamma juftlar, O(n²)
function countSlow(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) count++;
    }
  }
  return count;
}

test("chegaraviy: bo'sh va bitta element", () => {
  assert.deepEqual(sortAndCount([]), { sorted: [], count: 0 });
  assert.deepEqual(sortAndCount([7]), { sorted: [7], count: 0 });
});

test("kichik misol: [3, 1, 2] — 2 ta teskari juft", () => {
  assert.equal(sortAndCount([3, 1, 2]).count, 2);
});

test("teng qiymatlar teskari juft emas", () => {
  assert.equal(sortAndCount([5, 5, 5]).count, 0);
});

test("teskari tartib: n·(n−1)/2 juft", () => {
  const desc = Array.from({ length: 100 }, (_, i) => 100 - i);
  assert.equal(sortAndCount(desc).count, 4950);
});

test("sodda yechim bilan bir xil (urug'li tasodifiy)", () => {
  let seed = 14;
  const random = () => (seed = (seed * 16807) % 2147483647);
  const arr = Array.from({ length: 500 }, () => random() % 50);
  const fast = sortAndCount(arr);
  assert.equal(fast.count, countSlow(arr));
  assert.deepEqual(fast.sorted, arr.toSorted((x, y) => x - y));
});

✔ chegaraviy: bo'sh va bitta element (1.6188ms)
✔ kichik misol: [3, 1, 2] — 2 ta teskari juft (0.1944ms)
✔ teng qiymatlar teskari juft emas (0.1208ms)
✔ teskari tartib: n·(n−1)/2 juft (0.9866ms)
✔ sodda yechim bilan bir xil (urug'li tasodifiy) (4.5839ms)
ℹ tests 5
ℹ suites 0
ℹ pass 5
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 100.037

4-mashq: Amaliy tajriba — jadvalga ikki qator

kurs/mashqlar/14/MURAKKABLIK.md ga ikki qator qo'shing: merge sort (massiv) va merge sort (bog'langan ro'yxat). Vaqtni uch holat uchun yozing (eng yaxshi, o'rtacha, eng yomon) va xotirani ham. Yangi ustun oching: "Barqaror?".

| Masala | Yechim | Vaqt | Xotira | Barqaror? |
|---|---|---|---|---|
| Massivni saralash | merge sort | O(n log n) har holatda | O(n) | ha |
| Bog'langan ro'yxatni saralash | merge sort | O(n log n) | O(log n) stek | ha |

git add 14/MURAKKABLIK.md 14/29-merge
git commit -m "14/29: merge sort va teskari juftlar"

12. Real ishda

• JavaScript dvigatellari. V8 (Chrome, Node) ning sort i — merge sort'ning moslashuvchan avlodi (TimSort, endi PowerSort). Firefox'ning SpiderMonkey dvigateli ham merge sort ishlatadi. Ichki tafsilotlarni JS sort ichidan darsida ko'ramiz.
• Xotiraga sig'maydigan ma'lumot. 50 GB log faylni saralash kerak, kompyuterda esa 8 GB xotira. Faylni bo'laklarga bo'lib, har birini saralab diskka yoziladi, keyin bo'laklar birlashtiriladi — tashqi saralash (external sort). Ma'lumotlar bazalari katta ORDER BY ni shunday bajaradi.
• Oqimlarni birlashtirish. Bir nechta serverdan vaqt bo'yicha saralangan loglar keladi — ularni bitta lentaga qo'shish aynan merge.
• Intervyu. "Merge sort'ni yozing", "bog'langan ro'yxatni saralang" (LeetCode 148 "Sort List"), "teskari juftlarni sanang" — klassik savollar. Murakkablikni va barqarorlikni ayta olish shart.

Xulosa

• merge ikki saralangan ro'yxatni ikki ko'rsatkich bilan O(a + b) da birlashtiradi.
• Merge sort: o'rtadan bo'l, ikkala yarmini saralash, birlashtir. Asos holat — length <= 1.
• Vaqt doim O(n log n): log₂ n qatlam × har qatlamda n ish. O'lchovda n ×2 → vaqt ≈ ×2.
• Xotira — O(n) qo'shimcha (bog'langan ro'yxatda O(log n)). Rekursiya chuqurligi — log₂ n.
• <= barqarorlikni beradi: teng bo'lsa, chapdagisi oldin.

Keyingi dars: Quick sort — qo'shimcha massivsiz, joyida saralash: pivot atrofida bo'lish o'rtacha juda tez, lekin yomon pivot uni O(n²) ga tushiradi.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 2-bob (merge sort).
• Donald Knuth, "The Art of Computer Programming", 3-jild, 5-bob — birlashtirib saralash va tashqi saralash.
• LeetCode 148 "Sort List" — leetcode.com/problems/sort-list