Към съдържанието
wannacode

Merge sort и „разделяй и владей“

Накратко: Merge sort дели списъка на половини до единични елементи и ги слива подредени: O(n log n) сравнения при всеки вход, срещу O(n) допълнителна памет.

Проблем

„Подреди по цена“ при 100 000 продукта

Онлайн магазинът е пораснал до 100 000 продукта. Бутонът „Подреди по цена“ ползва insertion sort от простите сортирания.

При 1000 продукта insertion sort прави 256 555 сравнения, и страницата се отваря веднага. При 100 000 сравненията са около 2,5 милиарда. Продуктите са 100 пъти повече, а работата е 10 000 пъти повече: insertion sort е O(n²), защото всяка нова цена може да се сравни с всички преди нея.

Трябва ти начин, при който два пъти повече продукти дават малко повече от два пъти повече работа.

Идеята

Разделяй и владей

Как двама души подреждат купчина от 1000 фактури по сума? Делят я на две, всеки подрежда своята половина, после сливат: гледат горната фактура на двете купчини и взимат по-малката. Сливането на две подредени купчини е бързо: всяко сравнение слага една фактура на мястото ѝ.

А как всеки подрежда своята половина? Същото: дели я на две. И така, докато остане по една фактура. Една фактура вече е подредена.

Това е разделяй и владей (divide and conquer): задачата се дели на по-малки задачи от същия вид, те се решават със същия метод, а отговорите им се сглобяват. Сортирането, построено така, е merge sort (сортиране чрез сливане).

Методът вика сам себе си, затова това е рекурсия, както в урока „Рекурсия“. Дъното е списък с една цена: него няма какво да делиш.

Виж го

Делене до една цена и сливане обратно

mergeSort дели и вика себе си за двете половини. merge слива две подредени части. Гледай как осемте цени слизат до единични и как сливанията ги подреждат на връщане:

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


function merge(left, right) {
  const merged = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      merged.push(left[i]);
      i++;
    } else {
      merged.push(right[j]);
      j++;
    }
  }
  return merged.concat(left.slice(i), right.slice(j));
}
Стъпка по стъпка, с думи
  1. mergeSort получава 8 цени от каталога, неподредени.
  2. mid = 4. slice прави два нови масива: лявата половина [45, 12, 80, 33] и дясната [7, 61, 25, 50].
  3. Всяка половина вика mergeSort за себе си и се дели пак: 4 → 2 → 1.
  4. Част с една цена вече е подредена. Това е дъното на рекурсията: оттук извикванията започват да се връщат.
  5. merge слива две подредени части: сравнява първите им цени и взима по-малката. За двойка това е 1 сравнение, 4 за целия ред.
  6. Двойките стават четворки. Всяко сравнение пуска една цена надолу, затова на ред сравненията са по-малко от цените: тук 6.
  7. Последното сливане: [12, 33, 45, 80] с [7, 25, 50, 61]. i и j сочат първата невзета цена от всяка страна: 7 сравнения, 7 цени.
  8. Едната страна свърши. Остатъкът от другата (80) вече е подреден и отива накрая без сравнение.
  9. 3 нива деление (8 → 4 → 2 → 1), а на всяко ниво сливането минава всяка цена веднъж: 4 + 6 + 7 = 17 сравнения. При n цени нивата са log₂ n, затова работата е около n · log₂ n.
const prices = [45, 12, 80, 33, 7, 61, 25, 50];
console.log(`Преди: [${prices.join(", ")}]`);
console.log(`След: [${mergeSort(prices).join(", ")}]`);
Изход
Преди: [45, 12, 80, 33, 7, 61, 25, 50]
След: [7, 12, 25, 33, 45, 50, 61, 80]
slice(0, mid) прави нов масив с елементите от 0 до mid (без него). / в JavaScript дава дроб (9 / 2 е 4.5), затова Math.floor закръгля надолу.

Идеята

Защо е n · log n

Виж колко струва всяка част:

  • Сливането е O(n). Всяко сравнение слага една цена в резултата, а щом едната част свърши, остатъкът от другата отива накрая без сравнения. Две части с общо n цени искат най-много n − 1 сравнения.
  • Нивата са log₂ n. Всяко ниво дели на две: 8 цени дават 3 нива (8 → 4 → 2 → 1), 100 000 цени дават 17. log₂ n е „колко пъти n се дели на две до 1“.
  • На всяко ниво сливанията минават всички n цени веднъж. Двойките, четворките, половините: на ниво са различни групи, но заедно винаги са n.

Общо: най-много n · log₂ n сравнения. За 100 000 цени това е под 1 700 000. Bench преброява 1 536 292, около 1600 пъти по-малко от 2,5-те милиарда на insertion sort.

Пробвай

Предвиди изхода

Тук merge брои сравненията си. Двете части са подредени, а всяка цена отляво е по-малка от всяка отдясно:

let comparisons = 0;


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


console.log(`[${merge([10, 20, 30], [40, 50, 60]).join(", ")}]`);
console.log(`Сравнения: ${comparisons}`);
Отговор

Виж го

Измери го: merge sort срещу insertion sort

Пусни двата алгоритъма върху един и същ каталог с цени. Броят е на сравненията. Insertion sort при 100 000 не се пуска наистина (страницата щеше да замръзне): Bench го оценява по кривата.

  • Insertion sort O(n²)
  • Merge sort O(n log n)
Алгоритъмn = 10n = 1000n = 10 000n = 100 000
Insertion sort32256 55524 738 716≈ 2 473 871 600
Merge sort248679120 4831 536 292
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
function mergeSort(prices) {
  if (prices.length <= 1) {
    return prices;
  }
  const mid = Math.floor(prices.length / 2);
  const left = prices.slice(0, mid);
  const right = prices.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}


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

При 10 цени двата са почти равни. При 1000 merge sort прави 8679 сравнения срещу 256 555. Оттам нататък разликата расте с всяка нула: кривата на O(n²) е два пъти по-стръмна.

По-точно, за любопитните

Същите числа на твоя език. Каталогът идва от малък генератор със семе, затова е еднакъв при всяко пускане, на всеки език и в Bench. Броячът расте при всяко сравнение на две цени:

let comparisons = 0;


function catalog(n) {
  const prices = [];
  let x = 2026;
  for (let k = 0; k < n; k++) {
    x = (x * 48271) % 2147483647;
    prices.push(1 + (x % 10000));
  }
  return prices;
}


function insertionSort(prices) {
  for (let i = 1; i < prices.length; i++) {
    const key = prices[i];
    let j = i;
    while (j > 0) {
      comparisons++;
      if (prices[j - 1] <= key) {
        break;
      }
      prices[j] = prices[j - 1];
      j--;
    }
    prices[j] = key;
  }
}


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


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


for (const n of [10, 1000]) {
  comparisons = 0;
  insertionSort(catalog(n));
  console.log(`insertion sort, n = ${n}: ${comparisons} сравнения`);
}
for (const n of [10, 1000, 100000]) {
  comparisons = 0;
  mergeSort(catalog(n));
  console.log(`merge sort, n = ${n}: ${comparisons} сравнения`);
}
Изход
insertion sort, n = 10: 32 сравнения
insertion sort, n = 1000: 256555 сравнения
merge sort, n = 10: 24 сравнения
merge sort, n = 1000: 8679 сравнения
merge sort, n = 100000: 1536292 сравнения

Идеята

Цената: памет

Merge sort не е безплатен. Insertion sort мести цените в самия списък и не иска друго място. Merge sort при всяко делене прави нови масиви, а merge пише резултата в още един. Допълнителната памет е O(n): за 100 000 цени още толкова място.

Стекът от извиквания е плитък: по една рамка на ниво, около log₂ n. За 100 000 цени са 18 рамки.

Еднаквите цени остават в реда, в който са дошли: при равенство merge взима лявата (<=). Това се казва стабилност и има свой урок, „Стабилно сортиране“.

В JavaScript slice винаги прави нов масив. Затова този merge sort е кратък, но копира много. Вграденият sort на V8 е TimSort, вариант на merge sort, и е много по-бърз.

Пробвай

Намери грешката

Каталогът от осем продукта влиза, а излизат четири:

const prices = [45, 12, 80, 33, 7, 61, 25, 50];
console.log(`Преди: [${prices.join(", ")}]`);
console.log(`След: [${mergeSort(prices).join(", ")}]`);
Изход
Преди: [45, 12, 80, 33, 7, 61, 25, 50]
След: [33, 45, 50, 61]

На кой ред е грешката?

Избери реда с грешката.

Пробвай

Попълни

Цикълът в merge спира, щом едната част свърши. Какво пише на празното място, за да отиде остатъкът от дясната част накрая?

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

Упражнение

Два склада, един ценоразпис

Реши задачата в редактора си.

Два склада. Складът в София и складът във Варна пращат ценоразписите си, всеки вече подреден. Прочети двата реда и отпечатай един общ подреден ценоразпис. Не сортирай наново: ползвай merge от урока. Работата е O(n), не O(n log n).

Вход
12 33 45 80
7 25 50 61 99
Изход
Общо: 7 12 25 33 45 50 61 80 99

Още задачи

  • Преброй. Добави брояч на сравненията в merge и подреди осемте цени от сцената. Трябва да излезе 17.
  • От най-скъпото. Смени един знак, така че списъкът да излиза от най-скъпото към най-евтиното.
  • Без рекурсия. Слей съседните единични цени по двойки, после двойките по четворки, после четворките. Това е merge sort отдолу нагоре: същите сравнения, без стек от извиквания.

По-точно

Сливането извън сортирането

Сливането на подредени списъци е по-старо от merge sort: машините за перфокарти сливаха подредени тестета карти още през 30-те години. Днес се среща навсякъде, където данните вече са подредени: в git, в базите данни, при файлове, по-големи от паметта.

По-точно, за любопитните

Git. Git пази съдържанието на всяка папка (tree) подредено по име на файла. Когато сравнява две версии или слива клонове, той върви по двата подредени списъка едновременно, като merge: име, което го има само от едната страна, е добавен или изтрит файл, а еднаквите имена са файл и от двете страни, който се сравнява. Така проверката на папка е O(n), а не търсене на всеки файл в другия списък. Сливането на текста вътре във файла е друг алгоритъм (diff), до него ще стигнем в модула за динамично програмиране.

Външно сортиране. Логовете на сайта за година са 50 GB, а паметта е 8 GB. Сортирането чете по 1 GB, подрежда го в паметта и го записва като подредено парче на диска. После слива парчетата: от всяко чете само първия ред, взима най-малкия и продължава. Паметта стига за по един ред от всяко парче. Така подрежда големи файлове командата sort в Linux, а PostgreSQL пише в плана на заявката Sort Method: external merge, когато сортирането не се събира в паметта ѝ.

Мастър теоремата, като интуиция. Времето на merge sort се записва T(n) = 2 · T(n/2) + n: две задачи на половина плюс n за сливането. Нарисувай го като дърво: горе е n работа, на следващото ниво две по n/2, тоест пак n, и така log₂ n нива. Общо n · log₂ n. Мастър теоремата обобщава точно това сравнение: ако работата на ниво намалява надолу, горното ниво решава; ако расте, листата решават; ако е еднаква на всяко ниво, умножаваш по броя нива. Двоичното търсене е T(n) = T(n/2) + 1: по 1 на ниво, log₂ n нива, O(log n).

Вграденото сортиране. В JavaScript Array.prototype.sort на V8 (Chrome и Node) е TimSort, вариант на merge sort, който намира вече подредените парчета във входа. Как и защо, е в урока „Стабилно сортиране“.

Тест

Провери се

1. Защо merge sort е O(n log n)?
2. merge слива две подредени части по 4 цени. Колко сравнения прави най-много?
3. Какво плаща merge sort, което insertion sort не плаща?
4. Осемте цени вече са подредени. Колко сравнения прави всеки?
5. Колко нива на делене има merge sort за 100 000 цени?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·