Wstęp

Idąc za ciosem, studiując problem sortowania, mając za sobą podstawę oraz najprostsze z możliwych algorytmów, przejdźmy do czegoś odrobinę innego. Dziś opiszemy sobie algorytm wydajniejszy, korzystający z innego podejścia i z milszą dla oka złożonością. Czy aby na pewno szybszego? To się jeszcze okaże.

Technikalia: Warto dodać, że będziemy się poruszać w założeniu, że operujemy na obiektach, którym jest przypisany jakiś porządek całkowity. Więc nie rozpatrujemy przypadków granicznych, gdzie nie możemy porównać ze sobą dwóch obiektów w ciągu i będziemy już tak zakładać zawsze. Jeżeli jakiś algorytm będzie zakładał inaczej i będzie to warte wspomnienia - to explicite o tym wspomnimy.

Idea

Nazwa tego algorytmu może być myląca. Sam Von Neumann nie użył nawet słowa merge. Korzystał on z rozwiązania problemu meshingu, który sobie zaraz opiszemy. Rozwiązanie tego problemu przeniósł niejako na rozwiązanie problemu porządkowania/sortowania. Zaraz zobaczymy dlaczego. Pomysł na to próbuje się przypisywać idei, która zbudowała maszynę nazywaną z angielska "collator", która to podejmuje jeden z kroków (w wersji uproszczonej), z którego rozwiązanie tego problemu korzysta, ale jest to dosyć naciągane i przez nikogo nie potwierdzone. Swobodnie więc można sobie włożyć taki pomysł między bajki. Sam algorytm został opisany w 1948 roku, choć np. Donald Knuth twierdzi, że w 1945. Samemu nie udało mi się znaleźć artykułu z tego roku, który to potwierdzi, więc pozwolę sobie nie zaufać panu Donaldowi i poprosić o źródło takiej informacji, jeżeli ktoś jest w jego posiadaniu.

P.S. Opis obu problemów (merging, meshing) można znaleźć w: John von Neumann - Collected works. Vol.5 Design of Computers, Theory of Automata and Numerical Analysis (1963, Pergamon press), strona 197, podpunkt. 11.4.

Meshing - monotonizowanie ciągów

Problem meshingu (tak go będę nazywał, bo nie ma on polskiego odpowiednika), można zdefiniować w prosty sposób. Mamy \(2\) ciągi, ciąg \(A = (a_0, a_1, ..., a_n)\) oraz ciąg \(B = (b_0, b_1, ..., b_m)\). Oba te ciągi są monotoniczne. Monotoniczny, czyli stale jakiś. Stale rosnący, malejący, równy, nierosnący, niemalejący. Von Neumann nakłada na tę monotoniczność ograniczenie, które stanowi, że oba te ciągi muszą być niemalejące (później pokażemy, że można ten warunek odrobinę nagiąć). Mając to powiedziane, musimy doprowadzić do sytuacji, w której suma ciągów \(A\) i \(B\), czyli \(A + B = (a_0, a_1, ..., a_n, b_0, b_1, ..., b_m)\), również będzie monotoniczna. Problem ten dodatkowo wprowadza ciąg docelowy \(C\), który będzie zawierał już monotoniczną sumę \(A\) i \(B\). Jest to o tyle istotne, że jest to problem zdefiniowany w kontekście komputera czy też abstrakcyjnej maszyny liczącej, więc ciągi te mają fizyczną reprezentację w pamięci, którą trzeba wziąć pod uwagę.

A więc jak owy problem rozwiązać? Niejako łącząc oba te ciągi ze sobą w określony sposób. Wiemy, że oba są monotoniczne, niemalejące, więc są już ułożone w określonym porządku. Więc wyciągnijmy z \(A\) i \(B\) po pierwszym elemencie \(a_0\) i \(b_0\), porównajmy je ze sobą i mniejszy wrzućmy do \(C\) jako \(c_0\), a ten który wyszedł większy wsadźmy z powrotem tam, skąd go wzięliśmy. Jeden ciąg nam się tym samym skrócił. Następnie powtarzamy, znów bierzemy z \(A\) i \(B\) po pierwszym elemencie \(a_0\) i \(b_0\), porównujemy, mniejszy wrzucamy do \(C\) jako \(c_1\), większy odkładamy z powrotem. Proces ten powtarzamy, aż wyczerpiemy elementy z ciągu \(A\) lub \(B\), a z tego ciągu, w którym coś zostało, jako że jest to ciąg monotoniczny, po prostu przenosimy wszystkie elementy do \(C\). Mamy tym samym monotoniczny ciąg \(C\), który jest monotoniczną wersją sumy \(A + B\).

Teraz, jeżeli chcemy pozbyć się ograniczenia monotoniczności niemalejącej, musimy zauważyć, że taki porządek można dowolnie rozumieć i odwrócić wedle uznania, ale dla porządku spróbujmy to troszkę opisać.

Jeżeli rozumiemy, na czym polega pomysł na meshing, to widzimy, że ta sama monotoniczność ciągów jest konieczna. Niemalejąca? Już niekoniecznie. Dlaczego? No bo w sumie - czemu tak? Jedyna rzecz, która blokuje nas w procesie meshowania tych dwóch ciągów, to operacja porównania. To porównanie, które w oryginalnym opisie wybiera mniejszy element. Ale czy musi? Nie musi. Okazuje się, że jeżeli dołożymy do tego problemu porządek, wedle którego sobie stwierdzimy, który element jest mniejszy, to definicja tej mniejszości spada nam na kolana, więc możemy stwierdzić, że element większy jest mniejszy. Stąd moje wcześniejsze wspomnienie o tym, że porządek można rozumieć dowolnie. ALE! Zostaje nam jeszcze jeden problem. Jeżeli zaczniemy sobie przeprowadzać operację meshingu - dla testu albo ćwiczenia -zauważymy, że monotoniczność jest ściśle związana z tym porządkiem. Von Neumann określił ciąg niemalejący i wybierał element mniejszy. Jeżeli chcemy uogólnić ten problem, musimy mieć ciągi monotoniczne wedle jakiegoś porządku (albo uporządkowane wedle jakiegoś porządku) i porównanie tym właśnie porządkiem. Oczywiście zmieni nam się odrobinę pojęciowość, bo nie mamy już mniejszy/większy, tylko poprzedni i następny, ale łatwo tę pojęciowość sobie przenieść intuicyjnie, więc problem zdaje się mamy rozwiązany.

Przykład

Przyjmijmy ciąg \(A = (1, 2, 3, 4)\) oraz \(B = (7, 8, 9)\).

Weźmy po pierwszym elemencie \(a_0 = 1\), \(b_0 = 7\).

\(a_0\) jest mniejsze niż \(b_0\), więc dodajemy go do \(C\). Teraz więc mamy:

\(A = (2, 3, 4)\)
\(B = (7, 8, 9)\)
\(C = (1)\)

Weźmy następne \(a_0 = 2, b_0 = 7\)

\(a_0\) jest mniejsze niż \(b_0\), więc dodajemy go do \(C\). Teraz więc mamy:

\(A = (3, 4)\)
\(B = (7, 8, 9)\)
\(C = (1, 2)\)

Weźmy następne \(a_0 = 3, b_0 = 7\)

\(a_0\) jest mniejsze niż \(b_0\), więc dodajemy go do \(C\). Teraz więc mamy:

\(A = (4)\)
\(B = (7, 8, 9)\)
\(C = (1, 2, 3)\)

Weźmy następne \(a_0 = 4, b_0 = 7\)

\(a_0\) jest mniejsze niż \(b_0\), więc dodajemy go do \(C\). Teraz więc mamy:

\(A = ()\)
\(B = (7, 8, 9)\)
\(C = (1, 2, 3, 4)\)

W tym momencie skończył nam się ciąg \(A\), dlatego wszystko co zostało w \(B\) przerzucamy do \(C\). Po dokonaniu tego zostanie nam:

\(A = ()\)
\(B = ()\)
\(C = (1, 2, 3, 4, 7, 8, 9)\)

Mamy więc jeden monotoniczny ciąg z dwóch.

Sorting - monotonizowanie ciągu

Problem sortowania (sorting) von Neumann definiuje troszkę inaczej. Teraz mamy jeden niemonotoniczny ciąg \(A\) i problemem staje się stworzenie monotonicznego ciągu \(A^*\). Podejście do tego problemu będzie polegało na użyciu rozwiązania poprzedniego problemu. Mamy niemonotoniczny ciąg. Musimy sprawić, by się taki stał. Wiemy, że meshing dwóch monotonicznych ciągów da nam ciąg, który również będzie monotoniczny. Wiemy, że pary w ciągu zawsze będą monotoniczne i wiemy to dlatego, że zawsze będą ze sobą w jakimś porządku. Zawsze będą sobie równe albo jeden będzie większy albo mniejszy. Innej możliwości nie ma. Nie możemy jednak założyć, że będzie to ta sama monotoniczność. Możemy tak założyć, tylko jeżeli weźmiemy tylko podciągi o długości \(1\).

A więc bierzemy dwa podciągi o długości \(1\), które ze sobą sąsiadują, i meshujemy je w jeden monotoniczny. Następnie bierzemy dwa następne i znów je meshujemy je w jeden monotoniczny. Mamy już \(2\) monotoniczne ciągi, długości \(2\). Kontynuujemy ten proces, aż nie dojdziemy do końca ciągu \(A\). Jeżeli ciąg \(A\) jest nieparzystej długości, to po prostu na koniec parowania zostanie nam jeden ciąg o długości \(1\), który zostaje tak jak go napotkaliśmy.

Proces będzie wyglądał następująco. Na początku parujemy podciągi o długości \(1\):

Bierzemy element pierwszy \(a_0\) i drugi \(a_1\) i meshujemy je w jeden monotoniczny ciąg. W miejsce \(a_0\) i \(a_1\) wstawiamy już zmeshowany ciąg
Bierzemy element \(a_2\) i \(a_3\) i meshujemy je w jeden monotoniczny ciąg. W miejsce \(a_2\) i \(a_3\) wstawiamy już zmeshowany ciąg.
...
Teraz jeżeli ciąg jest długości parzystej, to:

Bierzemy element \(a_{n-1}\) i \(a_n\) i meshujemy je w jeden monotoniczny ciąg. W miejsce \(a_{n-1}\) i \(a_n\) wstawiamy już zmeshowany ciąg.

Jeżeli nieparzystej to:

Zostaje nam element \(a_n\) i nie mamy go z czym zmeshować, więc zostawiamy go samego.

Teraz parujemy ciągi o długości \(2\):

Bierzemy pierwszy ciąg \((a_0, a_1)\) i drugi \((a_2, a_3)\) i meshujemy je w jeden monotoniczny ciąg. W miejsca tych ciągów, wstawiamy ten zmeshowany.

Bierzemy pierwszy ciąg \((a_4, a_5)\) i drugi \((a_6, a_7)\) i meshujemy je w jeden monotoniczny ciąg. W miejsca tych ciągów, wstawiamy ten zmeshowany.

...

Teraz jeżeli ciąg jest długości parzystej, to:

Bierzemy pierwszy ciąg \((a_{n-3}, a_{n-2})\) i drugi \((a_{n-1}, a_{n})\) i meshujemy je w jeden monotoniczny ciąg. W miejsca tych ciągów, wstawiamy ten zmeshowany.

Jeżeli nieparzystej to:

Bierzemy pierwszy ciąg \((a_{n-2}, a_{n-1})\) i drugi \((a_{n})\) i meshujemy je w jeden monotoniczny ciąg. W miejsca tych ciągów, wstawiamy ten zmeshowany.

Następnie parujemy ciągi o długości \(4\), potem \(8\), itd. itd., aż w ten sposób uda się nam doprowadzić do sytuacji, gdy zostają nam \(2\) monotoniczne podciągi, które możemy zmeshować w jeden monotoniczny ciąg, tym samym niejako sortując ten ciąg wedle ustalonego porządku.

Przykład

Przyjmijmy ciąg \(A = (7, 6, 2, 1, 3, 4, 5)\).

Na początku parujemy podciągi o długości \(1\):

Bierzemy \((7)\) i \((6)\), meshujemy uzyskując \((6, 7)\), podmieniamy w \(A\). Teraz \(A = (6, 7, 2, 1, 3, 4, 5)\)
Bierzemy \((2)\) i \((1)\), meshujemy uzyskując \((1, 2)\), podmieniamy w \(A\). Teraz \(A = (6, 7, 1, 2, 3, 4, 5)\)
Bierzemy \((3)\) i \((4)\), meshujemy uzyskując \((3, 4)\), podmieniamy w \(A\). Teraz \(A = (6, 7, 1, 2, 3, 4, 5)\)
Bierzemy \((5)\) i ono nie ma pary, więc możemy uznać że bierzemy \(()\), uzyskując \((5)\), podmieniamy w \(A\). Teraz \(A = (6, 7, 1, 2, 3, 4, 5)\)

Następnie podciągi o długości \(2\):

Bierzemy \((6, 7)\) i \((1, 2)\), meshujemy uzyskując \((1, 2, 6, 7)\), podmieniamy w \(A\). Teraz \(A = (1, 2, 6, 7, 3, 4, 5)\)
Bierzemy \((3, 4)\) i \((5)\), meshujemy uzyskując \((3, 4, 5)\), podmieniamy w \(A\). Teraz \(A = (1, 2, 6, 7, 3, 4, 5)\)

Następnie podciągi o długości \(4\):

Bierzemy \((1, 2, 6, 7)\) i \((3, 4, 5)\), meshujemy uzyskując \((1, 2, 3, 4, 5, 6, 7)\), podmieniamy w \(A\). Teraz \(A = (1, 2, 3, 4, 5, 6, 7)\)

Podciągi o długości \(8\) są większe niż nasz ciąg pierwotny, więc kończymy, mając posortowany ciąg \(A\).

Sortowanie przez scalanie

Ten termin - mam wrażenie - został ukuty przez Donalda Knutha, który sortowanie von Neumannowskie ubrał w inne nazewnictwo, które niejako nawiązywało do maszyn zwanych "kolatorami", które to bezmyślnie przekładały kartę na kartę. Trochę jak maszynki od tasowania kart. Problem jednak opisał dokładnie w ten sam sposób, dodając mu odrobinę nomenklatury związanej bezpośrednio z informatyką.

Divide et impera

W internecie będzie się przewijać hasło "dziel i rządź", "divide and conquer", w kontekście tego algorytmu. Dlaczego? Albowiem trochę tak jest, ponieważ - jeżeli spojrzymy głębiej w sam proces sortowania - to jest to tak na prawdę meshing zaaplikowany wielokrotnie na podciągi. Czyli bierzemy problem sortowania i rozbijamy go na wiele podproblemów meshingu. Technicznie jest więc stwierdzeniem prawidłowym, że merge sort jest przykładem paradygmatu "dziel i rządź", ale sam Von Neumann mógł sobie nie zdawać z tego sprawy, albowiem ten termin został zaadaptowany w informatyce 20 lat później.

Implementacja

std::vector<int> mesh(std::span<int> seqA, std::span<int> seqB) {
    std::vector<int> output(seqA.size() + seqB.size());

    size_t lhsIndex = 0;
    size_t rhsIndex = 0;

    while (rhsIndex < seqB.size() && lhsIndex < seqA.size()) {
        if (seqB[rhsIndex] < seqA[lhsIndex]) {
            output.push_back(seqB[rhsIndex]);
            rhsIndex++;
        } else {
            output.push_back(seqA[lhsIndex]);
            lhsIndex++;
        }
    }

    for (size_t i = lhsIndex; i < seqA.size(); i++) {
        output.push_back(seqA[i]);
    }
    for (size_t i = rhsIndex; i < seqB.size(); i++) {
        output.push_back(seqB[i]);
    }
    
    return output;
}

def mesh(vecA: list[int], vecB: list[int]) -> list[int]:
    output: list[int] = []

    aIndex: int = 0
    bIndex: int = 0

    while aIndex < len(vecA) and bIndex < len(vecB):
        aElem = vecA[aIndex]
        bElem = vecB[bIndex]
        if aElem < bElem: 
            output.append(aElem)
            aIndex += 1
        else:
            output.append(bElem)
            bIndex += 1

    for i in range(aIndex, len(vecA)):
        output.append(vecA[i])
    for i in range(bIndex, len(vecB)):
        output.append(vecB[i])

    return output

Sorting

C++
Python 3

//For having safe subsequences as in python slice operator
std::span<int> subsequence(std::span<int> sequence, size_t from, size_t to) {
    //If requesting out of range beginning, return empty subsequence
    if (from >= sequence.size()) {
        return {};
    }
    //If requesting out of range ending, set last index
    if (to >= sequence.size()) {
        to = sequence.size();
    }
    return {sequence.data() + from, to - from};
}

void merge_sort(std::span<int> sequence) {
    for (size_t subseqSize = 1; subseqSize <= sequence.size(); subseqSize *= 2) {
        for (size_t offset = 0; offset < sequence.size(); offset += subseqSize * 2) {
            auto seqA = subsequence(sequence, offset, offset + subseqSize);
            auto seqB = subsequence(sequence, offset + subseqSize, offset + 2 * subseqSize);
            auto meshResult = mesh(seqA, seqB);
            for (size_t i = 0; i < meshResult.size(); i++) {
                sequence[offset + i] = meshResult[i];
            }
        }
    }
}

def merge_sort(sequence: list[int]):
    subseq_size = 1
    while subseq_size <= len(sequence):
        for offset in range(0, len(sequence), subseq_size * 2):
            seqA = sequence[offset: offset + subseq_size]
            seqB = sequence[offset + subseq_size: offset + 2 * subseq_size]
            meshed = mesh(seqA, seqB)
            for i in range(len(meshed)):
                sequence[offset + i] = meshed[i]
        subseq_size = subseq_size * 2

Czy można to zaimplementować lepiej? Z pewnością. Nam przyświeca jednak czytelność i zrozumienie tego, co opisaliśmy powyżej.

Złożoności

Złożoność obliczeniowa

Meshing

W tej operacji mamy porównywanie i wrzucanie do wyjściowego ciągu maksymalnie \(|A| + |B|\) razy, gdzie \(A\) i \(B\) to ciągi wejściowe. Więc złożoność obliczeniowa meshingu to \(O(|A| + |B|)\), czyli przyjemnie liniowa.

W kontekście sortowania, oba te podciągi będą maksymalnie długości sortowanego ciągu, powiedzmy \(n\) , stąd krok meshingu będzie miał złożoność \(O(n)\).

Sorting

Pętla zewnętrzna:

Pierwszym elementem naszego algorytmu jest parowanie podciągów długości \(2^k\), gdzie \(k = 1, 2, 3\)... aż do... No właśnie. Do czego? Otóż aż do tego, gdy \(2^k\) nie przekroczy rozmiaru ciągu. Więc skoro musimy znaleźć największe \(k\), gdzie \(2^k \leq n\), no to wystarczy obustronnie zlogarytmować podstawą \(2\), by otrzymać \(k \leq log_2{(n)}\). Maksymalna liczba iteracji wyniesie więc \(log_2{(n)}\). Będzie to pętla zewnętrzna, czyli

for (size_t subseqSize = 1; subseqSize <= sequence.size(); subseqSize *= 2)

Pętla wewnętrzna,

for (size_t offset = 0; offset < sequence.size(); offset += subseqSize * 2)

, będzie tworzyć podciągi, długości \(2\), potem \(4\) itd, dopóki nie przekroczy \(n\). Czyli najpierw wykona się \(\frac{n}{2}\) razy, potem \(\frac{n}{4}\) razy, dopóki mianownik będzie mniejszy od \(n\), czyli będzie tak kroczyć aż mianownik nie dojdzie do \(\frac{n}{2}\), jako że kroczymy mnożąc cały czas mianownik poprzedniego razy \(2\). Dostaniemy więc:

\(\frac{n}{2} + \frac{n}{4} + ... + \frac{n}{n / 2} = \displaystyle\sum_{m=1}^{\log_2{(n) - 1}}\frac{n}{2^m} = n - 2\)

Operacje pętli wewnętrznej prezentują się następująco:

auto seqA = subsequence(sequence, offset, offset + subseqSize);

ma złożonośc niezależną od \(n\), czyli \(O(1)\).

auto seqB = subsequence(sequence, offset + subseqSize, offset + 2 * subseqSize);

również. ma złożonośc niezależną od \(n\), czyli \(O(1)\).

auto meshResult = mesh(seqA, seqB);

ma złożoność \(O(|seqA| + |seqB|)\)

for (size_t i = 0; i < meshResult.size(); i++)

stworzy \(O(|seqA| + |seqB|)\) iteracji, a sam proces kopiowania

sequence[offset + i] = meshResult[i];

to w oczywisty sposób \(O(1)\).

Sumując wszystko do jednej złożoności mamy więc:

\(O(1) + O(1) + O(|seqA| + |seqB|) + O(|seqA| + |seqB|) + O(1) = O(2(|seqA| + |seqB|)) = O(|seqA| + |seqB|)\)

Pojawia się problem, bo mamy nieokreślone \(|seqA| + |seqB|\). Wiemy, że jest zależne od kroku wewnętrznej pętli. Musimy odrobinę skomplikować nasz wzór. (Warto tutaj dostrzec pewną zależność, a mianowicie, że pierdoły, które nie zależą od długości danych wejściowych, nie mają znaczenia. Warto to zaznaczyć ponieważ w następnych artykułach i krokach będziemy je pomijać, biorąc tę wiedzę za oczywistą.)

Każda wewnętrzna pętla iteruje się wedle ciągu \(\frac{n}{2} + \frac{n}{4} + ... + \frac{n}{n / 2}\) razy. W każdej z tej pętli \(|seqA| + |seqB|\) jest równa maksymalnie mianownikowi, bo najpierw pary, potem czwórki itd. Nazwijmy mianownik \(m\). Mamy więc sumę postaci:

\(\frac{n}{2}O(2) + \frac{n}{4}O(4) + ... + \frac{n}{n / 2}O(\frac{n}{2})\)

Którą przemianujemy wedle wcześniejszego nazewnictwa:

\(\frac{n}{2}O(2) + \frac{n}{4}O(4) + ... + \frac{n}{n / 2}O(\frac{n}{2}) = \displaystyle\sum_{m=1}^{\log_2{(n) - 1}}\frac{n}{2^m}O(m)\)

Teraz musimy zauważyć sobie jedną rzecz. Każde z tych mnożeń w opisanym szeregu, sprowadzi się dzięki własnościom notacji \(O\) do \(O(n)\), dlatego że:

\(\frac{n}{2}O(2) + \frac{n}{4}O(4) + ... + \frac{n}{n / 2}O(\frac{n}{2}) = O(\frac{2n}{2}) + O(\frac{4n}{4}) + ... + O(\frac{\frac{n}{2}n}{n / 2}) = O(n) + O(n) + ... + O(n)\)

Mamy więc \(m\) złożoności \(O(n)\), a nasze \(m\) jest ładnie określone jako \(\log_2{(n) - 1}\), a więc nasza złożoność całkowita wyniesie:

\(\displaystyle m \cdot O(n) = (\log_2(n) - 1) \cdot O(n) = O(n \cdot \log_2(n) - 1) = O(n \cdot \log_2(n) ) - O(1)\)

Czyli majestatyczne:

\(O(n \cdot \log_2(n) )\)

Należy tutaj dodać, że niezależnie od tego czy ciąg jest częściowo posortowany, czy też nie, złożoność zawsze pozostaje taka sama. Dlatego też złożoności średnie, najgorszego przypadku i optymistycznego przypadku, będą tutaj sobie tożsame.

Złożoność pamięciowa

Jakkolwiek cudownie byśmy nie zaimplementowali tego algorytmu, zawsze pozostaje jedna rzecz, której nie da się w nim ominąć. Ciąg wyjściowy operacji meshingu. Dlatego więc ZAWSZE będzie nam potrzebna dodatkowa pamięć, która ten ciąg pomieści. Ciąg ten będzie zawsze sumą dwóch podciągów, która sprowadzi się maksymalnie do przepołowionego ciągu wejściowego, czyli ciągi rozmiaru \(n\), a więc całkowita złożoność pamięciowa tego algorytmu wynosi:

\(O(n)\)

Inne właściwości

Rekursywność

Merge Sort jest na wskroś podatny na tę właściwość, albowiem studiując ten algorytm w internecie, napotkacie dziesiątki implementacji rekurencyjnych właśnie. Tutaj natomiast uniknęliśmy tego problemu. Więc można powiedzieć, że w naszym przypadku merge sort nie jest rekursywny, a w innym przypadku jest. W świetle jednak naszych dokonań musimy stwierdzić, że skoro udało nam się rekursji uniknąć i algorytm zaimplementować, nie jest to algorytm rekursywny.

Stabilność

Nasz algorytm jest na wskroś stabilny, albowiem zachowuje stały porządek, i w każdym kroku algorytmu kolejność równych elementów nie zmienia się.

Możliwość zrównoleglania

Jako że mamy wiele razy dokonywaną operację meshowania, na wielu podciągach niezależnych od siebie, można ten algorytm zrównoleglić. Ma to jednak sens tylko przy BARDZO DUŻEJ ilości danych, ponieważ orkiestracja równoległości przy małych rozmiarach ciągów znacznie przytłoczy czasem sam algorytm - natomiast przy bardzo dużej ilości danych mamy lepsze algorytmy i sposoby. Podsumowując, można, ale zupełnie się tego nie robi.

Adaptacyjność

Wspomniałem już, że złożoność będzie taka sama dla wszystkich przypadków ułożenia danych wejściowych, więc jeżeli można, to tylko przez triki w implementacjach. Odpowiedź teoretyczna natomiast brzmi nie.

Strumieniowość

Nie wszystkie dane są potrzebne, by rozpocząć wykonanie naszego algorytmu, bo najpierw potrzebujemy parki, potem czwórki itd. Więc swobodnie algorytm można karmić stopniowo. Jest on więc strumieniowy.

Metoda

Możemy powiedzieć - i większość się z tym zgodzi - że swobodnie można przypisać tu scalanie.

Porównanie i brak porównań

Tak, musimy porównywać.

Podsumowanie

Mamy za sobą pierwszy nietrywialny algorytm sortowania, dzięki któremu poznaliśmy odrobinę inne podejście do problemu. Mało tego, mamy pierwszy, który przełamał barierę złożoności kwadratowej. Mamy więc algorytm obiektywnie lepszy, ze względu na złożoność, od wszystkich poprzednio opisanych, co daje nam poczucie pewnego kroku naprzód. Wszystko wyliczone i zaimplementowane. Dziękuję za zaangażowanie i za uwagę! I do przeczytania w kolejnych artykułach! :)

Sortowanie przez scalanie (Merge Sort)

Żeby w pełni zrozumieć ten artykuł, warto najpierw zapoznać się z

Wstęp

Idea

Meshing - monotonizowanie ciągów

Przykład

Sorting - monotonizowanie ciągu

Przykład

Sortowanie przez scalanie

Divide et impera

Implementacja

Meshing

Sorting

Złożoności

Złożoność obliczeniowa

Meshing

Sorting

Złożoność pamięciowa

Inne właściwości

Rekursywność

Stabilność

Możliwość zrównoleglania

Adaptacyjność

Strumieniowość

Metoda

Porównanie i brak porównań

Podsumowanie

Komentarze

Komentarze

Odpowiadasz w wątku: