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

Код на:JavaC#PythonJavaScript

Накратко: 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 (сортиране чрез сливане).

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

Виж го

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

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

def merge_sort(prices):
    if len(prices) <= 1:
        return prices
    mid = len(prices) // 2
    left = prices[:mid]
    right = prices[mid:]
    return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

Стъпка по стъпка, с думи

1. merge_sort получава 8 цени от каталога, неподредени.
2. mid = 4. Срезът [:mid] прави два нови списъка: лявата половина [45, 12, 80, 33] и дясната [7, 61, 25, 50].
3. Всяка половина вика merge_sort за себе си и се дели пак: 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.

prices = [45, 12, 80, 33, 7, 61, 25, 50]
print(f"Преди: {prices}")
print(f"След: {merge_sort(prices)}")

Изход

Преди: [45, 12, 80, 33, 7, 61, 25, 50]
След: [7, 12, 25, 33, 45, 50, 61, 80]

prices[:mid] е срез: нов списък с елементите от 0 до mid (без него). // дели и закръгля надолу, затова mid е 4 и при 9 цени.

Идеята

Защо е 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 брои сравненията си. Двете части са подредени, а всяка цена отляво е по-малка от всяка отдясно:

comparisons = 0


def merge(left, right):
    global comparisons
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


print(merge([10, 20, 30], [40, 50, 60]))
print(f"Сравнения: {comparisons}")

Отговор

[10, 20, 30, 40, 50, 60]
Сравнения: 5

[10, 20, 30, 40, 50, 60]
Сравнения: 6

[10, 20, 30, 40, 50, 60]
Сравнения: 3

Провери

Виж го

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

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

• Insertion sort O(n²)
• Merge sort O(n log n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Insertion sort	32	256 555	24 738 716	≈ 2 473 871 600
Merge sort	24	8679	120 483	1 536 292

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

def merge_sort(prices):
    if len(prices) <= 1:
        return prices
    mid = len(prices) // 2
    left = prices[:mid]
    right = prices[mid:]
    return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

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

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

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

comparisons = 0


def catalog(n):
    prices = []
    x = 2026
    for _ in range(n):
        x = x * 48271 % 2147483647
        prices.append(1 + x % 10000)
    return prices


def insertion_sort(prices):
    global comparisons
    for i in range(1, len(prices)):
        key = prices[i]
        j = i
        while j > 0:
            comparisons += 1
            if prices[j - 1] <= key:
                break
            prices[j] = prices[j - 1]
            j -= 1
        prices[j] = key


def merge_sort(prices):
    if len(prices) <= 1:
        return prices
    mid = len(prices) // 2
    left = prices[:mid]
    right = prices[mid:]
    return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
    global comparisons
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


for n in [10, 1000]:
    comparisons = 0
    insertion_sort(catalog(n))
    print(f"insertion sort, n = {n}: {comparisons} сравнения")
for n in [10, 1000, 100000]:
    comparisons = 0
    merge_sort(catalog(n))
    print(f"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 взима лявата (<=). Това се казва стабилност и има свой урок, „Стабилно сортиране“.

В Python срезът prices[:mid] винаги прави нов списък. Затова този merge sort е кратък, но копира много. Вграденият sorted е TimSort, вариант на merge sort, написан на C, и е много по-бърз.

Пробвай

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

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

prices = [45, 12, 80, 33, 7, 61, 25, 50]
print(f"Преди: {prices}")
print(f"След: {merge_sort(prices)}")

Изход

Преди: [45, 12, 80, 33, 7, 61, 25, 50]
След: [33, 45, 50, 61]

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

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

1def merge_sort(prices):2 if len(prices) <= 1:3 return prices4 mid = len(prices) // 25 left = prices[:mid]6 right = prices[mid + 1:]7 return merge(merge_sort(left), merge_sort(right))

Провери

Пробвай

Попълни

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

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[:])
    return merged

Провери

Упражнение

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

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

Два склада. Складът в София и складът във Варна пращат ценоразписите си, всеки вече подреден. Прочети двата реда и отпечатай един общ подреден ценоразпис. Не сортирай наново: ползвай 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).

Вграденото сортиране. В Python sorted и list.sort ползват TimSort, вариант на merge sort, който намира вече подредените парчета във входа. Как и защо, е в урока „Стабилно сортиране“.

Тест

Провери се

1. Защо merge sort е O(n log n)?

Дели на две, а деленето на две е log nСравнява всяка цена с всяка друга, но само по веднъжДеленето дава log₂ n нива, а сливането на всяко ниво минава всички n цени веднъж

2. merge слива две подредени части по 4 цени. Колко сравнения прави най-много?

7168

3. Какво плаща merge sort, което insertion sort не плаща?

Памет: копията на половините и слетият резултат, O(n) допълнителноПовече сравнения при голямо nНе може да подреди еднакви цени

4. Осемте цени вече са подредени. Колко сравнения прави всеки?

И двата по 7Insertion sort 7, merge sort 12Insertion sort 28, merge sort 17

5. Колко нива на делене има merge sort за 100 000 цени?

1750 000100 000

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Big-O: как расте работата · Най-добър, среден и най-лош случай · Сложност по памет · Insertion sort и selection sort
• Продължава в: Quick sort и лошият пивот · Heap и heap sort · Counting sort и radix sort · Стабилно сортиране и вграденият sort
• Задачи по темата: Сортиране