Oddiy saralashlar: bubble, selection va insertion sort

Qisqacha: Uchta oddiy saralash — hammasi eng yomon holatda O(n²) va qo'shimcha xotirasiz (joyida). Bubble sort qo'shni juftlarni almashtiradi: katta son oxiriga "suzib chiqadi". Selection sort har qadamda qolgan qismdan eng kichigini tanlaydi: solishtirishlar doim n²/2, lekin almashtirishlar atigi n tagacha; beqaror. Insertion sort har elementni chapdagi saralangan qismga suqadi: barqaror, deyarli saralangan kirishda O(n). Shu sababli u real hayotda ham ishlaydi — kichik bo'laklar va deyarli tartiblangan ma'lumot uchun; Node 24 dagi V8 TimSort ham qisqa bo'laklarni insertion sort bilan saralaydi.

Bu darsda

• Bubble, selection va insertion sort'ni yoza olasiz va har birining o'zgarmas shartini aytib bera olasiz.
• Uchalasini solishtirishlar, yozishlar, barqarorlik va adaptivlik bo'yicha solishtira olasiz.
• n ikki baravar oshganda vaqt to'rt baravar oshishini o'lchab ko'rasiz.
• Oddiy saralash qachon foydali ekanini (kichik n, deyarli saralangan, oqim) bilasiz.

Oldin bilishingiz kerak: Saralash tushunchalari, Massiv xotirada va joyida amallar, Asosiy murakkablik sinflari.

1. Nega bu kerak?

JavaScript'da toSorted bor — nega saralashni o'zimiz yozamiz? Uch sabab.

Birinchisi — fikrlash usuli. Oddiy saralashlar o'zgarmas shart bilan ishlashni o'rgatadigan eng qulay misol: har sikl qadamida nima rost bo'lib qoladi va nega oxirida massiv saralangan bo'ladi. Bu ko'nikma har qanday sikl yozishda kerak.

Ikkinchisi — ular hali ham ishlaydi. «Bahor» oshxona ekranidagi buyurtmalar vaqt bo'yicha deyarli tartibda keladi; ba'zan bitta buyurtma kechikib qo'shiladi. Bunday ro'yxatni insertion sort bir o'tishda tuzatadi. TimSort ham ichida kichik bo'laklar uchun insertion sort'dan foydalanadi.

Uchinchisi — intervyu. "Bubble sort'ni yozing", "Nega selection sort beqaror?", "Insertion sort qachon yaxshi?" — boshlang'ich darajadagi eng ko'p savollar.

Avval kompyutersiz tasavvur qiling. Kun oxirida Sardorning stolida oltita chek turibdi, ularni summa bo'yicha tizish kerak. Odamlar buni uch xil qiladi:

• Qo'shnilarni almashtirish. Chapdan yurib, har ikki qo'shni chekka qaraysiz: chapdagisi katta bo'lsa — joyini almashtirasiz. Bir necha marta aylanib chiqasiz.
• Eng kichigini tanlash. Hamma chekni ko'rib, eng kichigini topasiz va birinchi o'ringa qo'yasiz. Keyin qolganlardan yana eng kichigini — shu tarzda oxirigacha.
• Karta tizish. Cheklarni bittalab olasiz va qo'lingizdagi tartibli dastaga o'z joyiga suqasiz.

Bu uch usul — bugungi uch algoritm: bubble, selection va insertion sort.

O'tgan darsda to'rt o'lchovni o'rgandik: vaqt, xotira, barqarorlik, adaptivlik. Bugun uchta algoritmni shu o'lchovlar bilan baholaymiz. Hammasi bir xil kirish bilan — buyurtma summalari, ming so'mda: 35, 28, 30, 5, 12, 41.

2. Bubble sort

2.1 G'oya

Bubble sort (pufakcha saralash) massiv bo'ylab yuradi va har qo'shni juftni solishtiradi: chapdagisi katta bo'lsa — joyini almashtiradi. Bir o'tishdan keyin eng katta son oxiriga yetib boradi — suvdagi pufakcha kabi yuqoriga "suzib chiqadi". Keyingi o'tish oxirgi elementga tegmaydi, ikkinchi kattasini o'z joyiga olib boradi. Shunday qilib, ko'pi bilan n − 1 o'tishda hamma son o'z joyiga tushadi.

Bitta muhim qo'shimcha: o'tish davomida birorta ham almashtirish bo'lmasa, massiv allaqachon saralangan — to'xtash mumkin. Bu swapped bayrog'i.

2.2 O'zgarmas shart

O'zgarmas shart (invariant) — siklning har qadamidan keyin rost bo'lib qoladigan gap. Bubble sort uchun: "k-o'tishdan keyin oxirgi k ta element — massivdagi eng katta k ta element, o'z yakuniy joylarida". Shart boshida rost (0 ta element), har o'tish uni bittaga kengaytiradi, n − 1 o'tishdan keyin esa u butun massivni qamraydi — demak, massiv saralangan.

O'zgarmas shart sikl to'g'riligini isbotlaydi, va qo'shimcha foydasi bor: ichki siklni end gacha qisqartirish mumkinligini ham aytadi — oxirgi qism allaqachon tayyor.

2.3 Baho

• Vaqt: eng yomon (teskari tartib) — n(n − 1)/2 solishtirish va shuncha almashtirish, O(n²). Eng yaxshi (saralangan) — bitta o'tish, n − 1 solishtirish, O(n).
• Xotira: O(1), joyida.
• Barqaror: ha — faqat qo'shnilar va faqat qat'iy > bo'lganda almashadi, teng elementlar bir-biridan o'tib ketmaydi.
• Adaptiv: qisman. Katta son o'ngga tez yuradi (bir o'tishda oxirigacha), lekin kichik son chapga bir o'tishda faqat bitta qadam suriladi. Ro'yxat oxiridagi bitta kichik son ("toshbaqa") butun n − 1 o'tishni talab qiladi — buni o'lchovda ko'ramiz.

3. Selection sort

3.1 G'oya

Selection sort (tanlab saralash) — o'tgan darsda beqarorlik misolida ko'rgan edik. Har qadamda qolgan qismni to'liq ko'rib, eng kichigini tanlaydi va uni navbatdagi o'ringa almashtiradi:

3.2 O'zgarmas shart

"i-qadamdan keyin a[0..i] — massivdagi eng kichik i + 1 ta element, saralangan tartibda". Bubble sort'dagi kabi, bu qism yakuniy: unga boshqa hech kim tegmaydi.

3.3 Baho

• Vaqt: har doim n(n − 1)/2 solishtirish — saralangan kirishda ham. Eng kichigini topish uchun qolgan qismni baribir to'liq ko'rish kerak. O(n²) — eng yaxshi holatda ham.
• Yozishlar: ko'pi bilan n − 1 ta almashtirish. Uchalasi ichida eng kami. Agar yozish qimmat bo'lsa (masalan, flesh-xotirada yoki og'ir obyektlarni ko'chirishda) — bu yutuq.
• Xotira: O(1).
• Barqaror: yo'q — uzoq masofaga almashtirish teng elementlar tartibini buzadi.
• Adaptiv: yo'q.

Tekshirib ko'ring: Selection sort [3, 1, 2] ni saralaganda nechta almashtirish qiladi?

4. Insertion sort

4.1 G'oya

Insertion sort (qo'shib saralash) — qo'ldagi kartalarni tizish usuli. Chap qo'lingizda kartalar allaqachon tartibda. O'ng qo'lingizdagi yangi kartani chapdan o'ngga qarab solishtirib, o'z joyiga suqasiz — kattaroq kartalar bir pog'ona suriladi.

Kodda: a[0..i-1] — saralangan. Yangi element key ni olamiz. Undan katta elementlarni bitta o'ngga suramiz (almashtirmaymiz — faqat yozamiz) va bo'shagan joyga key ni qo'yamiz:

4.2 O'zgarmas shart

"i-qadamdan keyin a[0..i] saralangan". Selection sort'dagidan farqi — bu qism yakuniy emas: keyin kelgan kichik son unga suqilib, elementlarni o'ngga surishi mumkin. Shuning uchun vizualda 5 kelganda 28, 30 va 35 hammasi surildi.

4.3 Baho

• Vaqt: eng yomon (teskari) — n(n − 1)/2, O(n²). Eng yaxshi (saralangan) — har element uchun bitta solishtirish, O(n).
• Aniqrog'i: ish = n + inversiyalar soni. Inversiya — noto'g'ri tartibda turgan juft (chapdagisi katta). Har surish aynan bitta inversiyani yo'q qiladi. Deyarli saralangan massivda inversiyalar kam — demak, ish ham kam.
• Xotira: O(1).
• Barqaror: ha — a[j] > key qat'iy: teng element key dan o'tib ketmaydi.
• Adaptiv: ha — va bu uning asosiy kuchi.
• Oqimga mos (online): elementlar birma-bir kelsa, har birini darhol saralangan qismga suqish mumkin — butun ro'yxatni kutish shart emas.

Tekshirib ko'ring: [2, 3, 4, 5, 1] massivida nechta inversiya bor? Insertion sort nechta surish qiladi?

5. Sanaymiz: solishtirish va yozish

Avval uchalasini bir jadvalda eslab olaylik:

Endi jadvalni raqamlar bilan tekshiramiz.

Uchala algoritmga hisoblagich qo'shib, 1 000 elementli to'rt xil kirishda sanadik. "Yozish" — massivga har yozish (almashtirish — 2 ta, surish — 1 ta):

// har saralash { cmp: solishtirishlar, writes: yozishlar } qaytaradi
function bubble(nums) {
  const a = [...nums];
  let cmp = 0;
  let writes = 0;
  for (let end = a.length - 1; end > 0; end--) {
    let swapped = false;
    for (let j = 0; j < end; j++) {
      cmp++;
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        writes += 2;
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return { cmp, writes };
}

function selection(nums) {
  const a = [...nums];
  let cmp = 0;
  let writes = 0;
  for (let i = 0; i < a.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < a.length; j++) {
      cmp++;
      if (a[j] < a[min]) min = j;
    }
    if (min !== i) {
      [a[i], a[min]] = [a[min], a[i]];
      writes += 2;
    }
  }
  return { cmp, writes };
}

function insertion(nums) {
  const a = [...nums];
  let cmp = 0;
  let writes = 0;
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && (cmp++, a[j] > key)) {
      a[j + 1] = a[j];
      writes++;
      j--;
    }
    a[j + 1] = key;
    writes++;
  }
  return { cmp, writes };
}

const n = 1000;
const sorted = Array.from({ length: n }, (_, i) => i);
const nearly = [...sorted];
for (let k = 0; k < 10; k++) {
  const i = k * 97; // 10 ta qo'shni juft joyini almashtiramiz
  [nearly[i], nearly[i + 1]] = [nearly[i + 1], nearly[i]];
}
let seed = 2026;
const random = sorted.map(() => (seed = (seed * 16807) % 2147483647));
const reversed = sorted.toReversed();
const inputs = { random, sorted, nearly, reversed };

for (const [name, input] of Object.entries(inputs)) {
  const row = [bubble, selection, insertion].map((sort) => {
    const { cmp, writes } = sort(input);
    return `${cmp}/${writes}`;
  });
  console.log(name.padEnd(9), row.join("  "));
}

Konsolda (har katakda — solishtirishlar/yozishlar; ustunlar: bubble, selection, insertion):

random    499122/509342  499500/1990  255668/255670
sorted    999/0  499500/0  999/999
nearly    1997/20  499500/20  1008/1009
reversed  499500/999000  499500/1000  499500/500499

Jadvaldan to'rt xulosa:

1. Selection har qatorda 499 500 solishtirish — kirishga befarq. Yozishlari esa eng kam (2 mingdan oshmaydi).
2. Insertion aralash kirishda bubble'dan ikki baravar kam ish qildi: 255 668 ga qarshi 499 122. Sababi — u inversiyalarni sanaydi (≈ n²/4), bubble esa deyarli hamma juftni solishtiradi.
3. Deyarli saralangan (10 ta qo'shni juft almashgan) kirishda insertion — 1 008 solishtirish, deyarli n. Bubble ham yaxshi (1 997) — chunki buzilish kichik va qo'shnilar orasida.
4. Teskari — hamma uchun eng yomon: 499 500 solishtirish.

Bubble'ning "toshbaqa" muammosini alohida tekshirdik: [1, 2, …, 999, 0] — eng kichik son oxirida. Bubble — 499 500 solishtirish (n − 1 o'tish, har birida 0 faqat bir qadam chapga siljiydi). Insertion — 1 997: 0 ni bir martada boshiga suradi. Eng katta son boshida bo'lsa ([999, 0, 1, …]), ikkalasi ham 1 997 — bubble uni bir o'tishda oxiriga olib boradi.

6. O'lchov: n ikki baravar — vaqt to'rt baravar

Aralash sonlar bilan vaqtni o'lchadik (benchmarking darsidagi usul: har n alohida jarayonda, isitish, 5 o'lchov medianasi). Saralash joyida — har o'lchovda kirish qaytadan yasaladi:

Selection va insertion'da n ikki baravar — vaqt ≈ 3,8–4,2 baravar: kvadratik o'sish aniq ko'rinadi. Bubble esa to'rt baravardan ham ko'p o'sdi (8 000 dan keyin ×5,6–6,1; ikkinchi o'lchovda ham shunday chiqdi). Big-O sinfi o'sha — O(n²), lekin bubble eng ko'p yozish qiladi va massiv kattalashgach har yozish qimmatlashadi (ehtimol protsessor keshiga sig'may qolish ta'siri). Amaliy xulosa: uchta O(n²) ichida bubble — eng sekini, insertion — eng tezi.

Va insertion sort'ning kuchli tomoni — deyarli saralangan kirish (10 ta juft almashgan):

Chiziqli: n ikki baravar — vaqt ikki baravar. 800 000 element 2,5 ms da — aralash 16 000 elementdan 20 baravar tez.

Taqqoslash uchun: o'tgan darsda toSorted 100 000 aralash sonni ≈ 27 ms da saraladi. Insertion sort 16 000 ga 56 ms sarfladi; 100 000 da u taxminan 2 soniya olardi (n² bo'yicha bashorat: 56 × 39 ≈ 2 200 ms).

7. Qachon ishlatiladi?

Gibrid algoritmlar insertion sort'ni ichiga oladi. Node 24 dagi V8 TimSort kirishni yugurishlarga bo'ladi va qisqa yugurishlarni (32–64 elementgacha) ikkilik qidiruvli insertion sort bilan uzaytiradi, keyin birlashtiradi. C++ standart kutubxonasidagi std::sort ham kichik bo'laklar uchun insertion sort'ga o'tadi. Kichik n da O(n²) ning n² i kichik, insertion'ning o'zgarmas ko'paytuvchisi esa merge sort'nikidan kichik.

Tekshirib ko'ring: Kechagi saralangan 10 000 ta buyurtmaga bugun 5 ta yangi buyurtma oxiriga qo'shildi. Ro'yxatni qayta saralash uchun insertion sort taxminan nechta solishtirish qiladi: 50 milliongami yoki 10–60 mingtagami?

8. Chegaraviy holatlar

• Bo'sh va bitta element. Uchala kodda ham tashqi sikl bir marta ham aylanmaydi — massiv o'zgarishsiz qaytadi.
• Takroriy qiymatlar. Bubble va insertion — qat'iy > bilan barqaror. >= yozsangiz, teng elementlar bir-biridan o'tib ketadi: natija baribir saralangan, lekin barqarorlik yo'qoladi.
• Manfiy sonlar va kasrlar. </> ularni to'g'ri solishtiradi. Lekin satrlarni sonlardek solishtirish — boshqa gap: "10" < "9" — true (satr bo'yicha). Kirish turini tekshiring.
• Hammasi teng. Bubble — bitta o'tish va to'xtash; insertion — n − 1 solishtirish; selection — baribir n²/2.
• NaN. NaN bilan har qanday solishtirish false — NaN joyidan qimirlamaydi va atrofidagi tartib buziladi. Saralashdan oldin bunday qiymatlarni filtrlang.

9. Ko'p uchraydigan xatolar

9.1 Ichki sikl chegarasi

Bubble sort'da ichki sikl j < a.length bo'lsa, oxirgi qadamda a[j + 1] — undefined. 35 > undefined — false, xato chiqmaydi, lekin keraksiz solishtirish bo'ladi; j < end dan oshib ketish esa allaqachon tayyor qismni ham qayta tekshiradi. Qoida: qo'shnilarni solishtirganda oxirgi indeks — end - 1.

9.2 key ni saqlamaslik

Insertion sort'da key = a[i] ni oldindan saqlamasangiz, birinchi surish (a[j + 1] = a[j], ya'ni a[i] = a[i - 1]) uni ustidan yozib yuboradi va qiymat yo'qoladi. Tuzatish: surishdan oldin const key = a[i].

9.3 Selection'da min ni qayta tiklamaslik

let min = i tashqi siklning ichida bo'lishi shart. Tashqarida e'lon qilinsa, eski indeks keyingi qadamga o'tadi va allaqachon saralangan qismdagi element "eng kichik" deb tanlanadi.

9.4 Kiruvchi massivni buzish

Darsdagi funksiyalar [...nums] bilan nusxa oladi. Nusxasiz yozilsa, chaqiruvchining massivi o'zgaradi — sort kabi. Bu ham to'g'ri tanlov bo'lishi mumkin, lekin funksiya nomi va hujjatida aniq ayting (Saralash tushunchalari: sort va toSorted).

10. Mashqlar

1-mashq (oson): O'tishlarni sanang

Darsdagi bubbleSort (swapped bilan) [1, 2, 3, 5, 4] massivida nechta o'tish qiladi? Birinchi o'tish 5 va 4 ni almashtiradi. Ikkinchi o'tishda almashtirish bo'lmaydi va sikl to'xtaydi. O'tishlar soni:

2-mashq (o'rta): Kechikkan buyurtma

Oshxona ekranidagi buyurtmalar vaqt bo'yicha saralangan: ["12:05", "12:07", "12:10", "12:12"]. Kechikib "12:06" keldi va oxiriga qo'shildi. Insertion sort'ning bitta qadamini — faqat oxirgi elementni joyiga suqishni — insertLast(times) funksiyasi qilib yozing (massivni joyida o'zgartirsin). Nechta surish bo'ladi?

function insertLast(times) {
  const i = times.length - 1;
  const key = times[i];
  let j = i - 1;
  let shifts = 0;
  while (j >= 0 && times[j] > key) {
    times[j + 1] = times[j]; // kechroq vaqt bir o'ngga
    j--;
    shifts++;
  }
  times[j + 1] = key;
  return shifts;
}

const times = ["12:05", "12:07", "12:10", "12:12", "12:06"];
console.log(insertLast(times)); // 3
console.log(times.join(" ")); // 12:05 12:06 12:07 12:10 12:12

3-mashq (qiyin): Taqqoslash funksiyali insertion sort va testlar

kurs/mashqlar/14/28-oddiy-saralash/sort.test.mjs faylida insertionSort(items, cmp) ni yozing: toSorted dagi kabi taqqoslash funksiyasini qabul qilsin (standart — sonlar o'sishi), asl massivni o'zgartirmasin va { sorted, comparisons } qaytarsin. Testlar (node:test): sonlar takror va manfiylar bilan; barqarorlik (toSorted bilan bir xil natija); saralangan 1 000 elementda 999 solishtirish; bo'sh va bitta element.

// kurs/mashqlar/14/28-oddiy-saralash/sort.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

// cmp(a, b) — toSorted dagi kabi: manfiy — a oldin
function insertionSort(items, cmp = (a, b) => a - b) {
  const a = [...items];
  let comparisons = 0;
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    // qat'iy > 0: teng element key dan o'tib ketmaydi — barqaror
    while (j >= 0 && (comparisons++, cmp(a[j], key) > 0)) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return { sorted: a, comparisons };
}

const orders = [
  { id: 1, status: "tayyor" },
  { id: 2, status: "kutmoqda" },
  { id: 3, status: "tayyor" },
  { id: 4, status: "kutmoqda" },
];
const rank = { kutmoqda: 0, tayyor: 1 };
const byStatus = (a, b) => rank[a.status] - rank[b.status];

test("sonlar o'sish tartibida, takrorlar va manfiylar bilan", () => {
  const { sorted } = insertionSort([30, -5, 12, 30, 0, 7]);
  assert.deepEqual(sorted, [-5, 0, 7, 12, 30, 30]);
});

test("barqaror: teng holatlilar kelgan tartibida", () => {
  const { sorted } = insertionSort(orders, byStatus);
  assert.deepEqual(sorted.map((o) => o.id), [2, 4, 1, 3]);
  assert.deepEqual(sorted, orders.toSorted(byStatus));
});

test("adaptiv: saralangan kirishda n − 1 solishtirish", () => {
  const nums = Array.from({ length: 1000 }, (_, i) => i);
  assert.equal(insertionSort(nums).comparisons, 999);
});

test("bo'sh va bitta element; asl massiv o'zgarmaydi", () => {
  assert.deepEqual(insertionSort([]).sorted, []);
  assert.deepEqual(insertionSort([35000]).sorted, [35000]);
  const input = [3, 1, 2];
  insertionSort(input);
  assert.deepEqual(input, [3, 1, 2]);
});

✔ sonlar o'sish tartibida, takrorlar va manfiylar bilan (1.2579ms)
✔ barqaror: teng holatlilar kelgan tartibida (0.1835ms)
✔ adaptiv: saralangan kirishda n − 1 solishtirish (0.3711ms)
✔ bo'sh va bitta element; asl massiv o'zgarmaydi (0.8101ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 79.4716

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga uchta saralashni qo'shing. Vaqt ustunida eng yaxshi va eng yomon holatni ham yozing, alohida ustunlarda — barqarorlik va adaptivlik.

| Saralash | Vaqt (eng yaxshi / eng yomon) | Xotira | Barqaror / adaptiv |
|---|---|---|---|
| Bubble | O(n) / O(n²) | O(1) | ha / qisman |
| Selection | O(n²) / O(n²) | O(1) | yo'q / yo'q |
| Insertion | O(n) / O(n²) | O(1) | ha / ha |

git add 14/MURAKKABLIK.md 14/28-oddiy-saralash
git commit -m "14/28: oddiy saralashlar, insertion sort testlari"

11. Real ishda

• Kutubxonalar ichida. TimSort (V8, Python, Java'da obyektlar uchun) qisqa yugurishlarni insertion sort bilan saralaydi; introsort (C++) kichik bo'laklarda insertion sort'ga o'tadi. Siz Node 24 da toSorted chaqirganingizda ham ichkarida insertion sort ishlaydi.
• Oqim va real vaqt. Kelayotgan voqealar, o'yin reytingi, oshxona navbati — har yangi element saralangan ro'yxatga suqiladi. Ro'yxat katta bo'lsa, joyini binary search bilan topish va keyin surish odatiy usul.
• Cheklangan qurilmalar. Mikrokontrollerlarda, xotira juda oz joyda — rekursiyasiz, joyida ishlaydigan oddiy saralash ba'zan yagona variant.
• Intervyu. "Bubble sort'ni yozing va uni yaxshilang" (swapped), "Selection sort nega beqaror?", "Insertion sort qachon O(n)?", "Inversiya nima?" — klassik boshlang'ich savollar.

Xulosa

• Bubble — qo'shnilarni almashtiradi, swapped bilan saralangan kirishda O(n); barqaror; "toshbaqa" (oxirdagi kichik son) uchun sekin.
• Selection — har doim n²/2 solishtirish, lekin n − 1 tagacha almashtirish; beqaror, adaptiv emas.
• Insertion — chapdagi saralangan qismga suqadi; ish = n + inversiyalar; barqaror, adaptiv, oqimga mos.
• O'zgarmas shart sikl to'g'riligini isbotlaydi: bubble va selection'da tayyor qism yakuniy, insertion'da — yo'q.
• O'lchov: aralash 16 000 son — 424 / 89 / 56 ms (bubble / selection / insertion), n ×2 → vaqt ×4; deyarli saralangan 800 000 sonni insertion ≈ 2,5 ms da saraladi.

Keyingi dars: Merge sort — massivni ikkiga bo'lib, saralab, birlashtirish: har doim O(n log n) va barqaror; O(n) qo'shimcha xotira narxi va bog'langan ro'yxatni saralash.

Manbalar

• Donald E. Knuth, "The Art of Computer Programming", 3-jild ("Sorting and Searching"), 2-nashr, Addison-Wesley, 1998 — "Internal Sorting" bo'limi (inversiyalar, insertion va exchange saralashlar).
• V8 blog: "Getting things sorted in V8" (2018) — TimSort va ikkilik insertion sort — v8.dev/blog/array-sort
• Tim Peters, "listsort.txt" — minrun va binary insertion sort — github.com/python/cpython