Sortowanie scalające — Merge sort

Scal sortuj
	Przykład sortowania przez scalanie. Najpierw podziel listę na najmniejszą jednostkę (1 element), a następnie porównaj każdy element z sąsiednią listą, aby posortować i scalić dwie sąsiednie listy. Na koniec wszystkie elementy są sortowane i łączone.
Klasa	Algorytm sortowania
Struktura danych	Szyk
Wydajność w najgorszym przypadku
Wydajność w najlepszym przypadku	typowy, naturalny wariant
Średnia wydajność
Najgorsza złożoność przestrzeni	sumaryczny z pomocniczymi, pomocniczy z połączonymi listami

W informatyce , merge sort (również często pisane jako mergesort ) jest skutecznym, ogólnego przeznaczenia, a porównanie oparte algorytm sortowania . Większość implementacji tworzy stabilny sort , co oznacza, że kolejność równych elementów jest taka sama na wejściu i wyjściu. Sortowanie przez scalanie to algorytm dziel i rządź, który został wymyślony przez Johna von Neumanna w 1945 roku. Szczegółowy opis i analiza sortowania przez scalanie od dołu do góry pojawiły się w raporcie Goldstine i von Neumann już w 1948 roku.

Algorytm

Koncepcyjnie sortowanie przez scalanie działa w następujący sposób:

Podziel nieposortowaną listę na n podlist, z których każda zawiera jeden element (lista jednego elementu jest uważana za posortowaną).
Wielokrotnie scalania listy zagnieżdżone w celu wytworzenia nowych listy zagnieżdżone posortowane dopóki istnieje tylko jeden podlistę pozostały. To będzie posortowana lista.

Implementacja odgórna

Przykładowy kod podobny do C używający indeksów dla algorytmu sortowania odgórnego przez scalanie, który rekursywnie dzieli listę (nazywaną w tym przykładzie przebiegami ) na podlisty, aż rozmiar podlisty wynosi 1, a następnie łączy te podlisty w celu utworzenia posortowanej listy. Unika się kroku wstecznego poprzez zmianę kierunku łączenia na każdym poziomie rekurencji (z wyjątkiem początkowej jednorazowej kopii). Aby pomóc to zrozumieć, rozważ tablicę z dwoma elementami. Elementy są kopiowane do B[], a następnie łączone z powrotem do A[]. Jeśli są cztery elementy, po osiągnięciu dolnego poziomu rekurencji, pojedyncze przebiegi z A[] są scalane z B[], a następnie na następnym wyższym poziomie rekurencji te dwuelementowe przebiegi są scalane z A[ ]. Ten wzorzec jest kontynuowany na każdym poziomie rekurencji.

// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // one time copy of A[] to B[]
    TopDownSplitMerge(B, 0, n, A);   // sort data from B[] into A[]
}

// Split A[] into 2 runs, sort both runs into B[], merge both runs from B[] to A[]
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if (iEnd - iBegin <= 1)                     // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sort the left  run
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
void TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
    i = iBegin, j = iMiddle;
 
    // While there are elements in the left or right runs...
    for (k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(A[], iBegin, iEnd, B[])
{
    for (k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

Sortowanie całej tablicy jest realizowane przez TopDownMergeSort(A, B, length(A)) .

Wdrażanie oddolne

Przykład kodu podobnego do C używającego indeksów dla algorytmu sortowania od dołu do góry, który traktuje listę jako tablicę n podlist ( w tym przykładzie nazywanych przebiegami ) o rozmiarze 1 i iteracyjne scala podlisty tam i z powrotem między dwoma buforami:

// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
{
    // Each 1-element run in A is already "sorted".
    // Make successively longer sorted runs of length 2, 4, 8, 16... until the whole array is sorted.
    for (width = 1; width < n; width = 2 * width)
    {
        // Array A is full of runs of length width.
        for (i = 0; i < n; i = i + 2 * width)
        {
            // Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
            // or copy A[i:n-1] to B[] ( if (i+width >= n) )
            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        // Now work array B is full of runs of length 2*width.
        // Copy array B to array A for the next iteration.
        // A more efficient implementation would swap the roles of A and B.
        CopyArray(B, A, n);
        // Now array A is full of runs of length 2*width.
    }
}

//  Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1  ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // While there are elements in the left or right runs...
    for (k = iLeft; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

void CopyArray(B[], A[], n)
{
    for (i = 0; i < n; i++)
        A[i] = B[i];
}

Implementacja odgórna z wykorzystaniem list

Pseudokod dla algorytmu sortowania odgórnego przez scalanie, który rekursywnie dzieli listę wejściową na mniejsze podlisty, aż podlisty zostaną posortowane w trywialny sposób, a następnie scala podlisty, zwracając się w górę łańcucha wywołań.

function merge_sort(list m) is
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the first half and second half of the list.
    // This assumes lists start at index 0.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i < (length of m)/2 then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

W tym przykładzie funkcja scalania łączy lewą i prawą podlistę.

function merge(left, right) is
    var result := empty list

    while left is not empty and right is not empty do
        if first(left) ≤ first(right) then
            append first(left) to result
            left := rest(left)
        else
            append first(right) to result
            right := rest(right)

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    while left is not empty do
        append first(left) to result
        left := rest(left)
    while right is not empty do
        append first(right) to result
        right := rest(right)
    return result

Implementacja oddolna z wykorzystaniem list

Pseudokod dla algorytmu sortowania przez scalanie od dołu do góry, który używa małej tablicy o stałym rozmiarze referencji do węzłów, gdzie array[i] jest odwołaniem do listy o rozmiarze 2 ⁱ lub nil . węzeł jest odniesieniem lub wskaźnikiem do węzła. Funkcja merge() byłaby podobna do tej pokazanej w przykładzie listy scalania od góry do dołu, łączy dwie już posortowane listy i obsługuje listy puste. W tym przypadku merge() użyje node jako parametrów wejściowych i zwróci wartość.

function merge_sort(node head) is
    // return if empty list
    if head = nil then
        return nil
    var node array[32]; initially all nil
    var node result
    var node next
    var int  i
    result := head
    // merge nodes into array
    while result ≠ nil do
        next := result.next;
        result.next := nil
        for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do
            result := merge(array[i], result)
            array[i] := nil
        // do not go past end of array
        if i = 32 then
            i -= 1
        array[i] := result
        result := next
    // merge array into single list
    result := nil
    for (i = 0; i < 32; i += 1) do
        result := merge(array[i], result)
    return result

Naturalne sortowanie przez scalanie

Naturalne sortowanie przez scalanie jest podobne do sortowania przez scalanie od dołu do góry, z wyjątkiem tego, że wykorzystywane są wszelkie naturalnie występujące przebiegi (posortowane sekwencje) w danych wejściowych. Mogą być wykorzystywane zarówno monotoniczne, jak i bitoniczne (naprzemienne ruchy w górę/w dół), z listami (lub równoważnymi taśmami lub plikami) będącymi wygodnymi strukturami danych (używanymi jako kolejki FIFO lub stosy LIFO ). W sortowaniu przez scalanie od dołu do góry punkt początkowy zakłada, że każdy przebieg ma długość jednego elementu. W praktyce losowe dane wejściowe będą miały wiele krótkich przebiegów, które akurat zostaną posortowane. W typowym przypadku naturalne sortowanie przez scalanie może nie wymagać tylu przebiegów, ponieważ jest mniej przebiegów do scalenia. W najlepszym przypadku dane wejściowe są już posortowane (tj. są jednym przebiegiem), więc naturalne sortowanie przez scalanie wymaga tylko jednego przejścia przez dane. W wielu praktycznych przypadkach występują długie, naturalne przebiegi iz tego powodu naturalne sortowanie przez scalanie jest wykorzystywane jako kluczowy składnik Timsort . Przykład:

Start       :  3  4  2  1  7  5  8  9  0  6
Select runs : (3  4)(2)(1  7)(5  8  9)(0  6)
Merge       : (2  3  4)(1  5  7  8  9)(0  6)
Merge       : (1  2  3  4  5  7  8  9)(0  6)
Merge       : (0  1  2  3  4  5  6  7  8  9)

Formalnie mówi się, że naturalne sortowanie przez scalanie to Runs -optimal, gdzie jest liczba przebiegów w minus jeden. ${\ Displaystyle {\ mathtt {działa}} (L)}$ ${\ Displaystyle L}$

Sortowanie zastępowania turnieju służy do zbierania początkowych przebiegów dla zewnętrznych algorytmów sortowania.

Analiza

Rekurencyjny algorytm sortowania przez scalanie używany do sortowania tablicy 7 wartości całkowitych. Są to kroki, które wykonałby człowiek, aby emulować sortowanie przez scalanie (od góry do dołu).

W sortowaniu n obiektów sortowanie przez scalanie ma średnią i najgorszą wydajność wynoszącą O ( n log n ). Jeżeli czas wykonania sortowania przez scalanie dla listy o długości n wynosi T ( n ), to relacja rekurencji T ( n ) = 2 T ( n /2) + n wynika z definicji algorytmu (zastosuj algorytm do dwóch listy o połowę mniejsze od oryginalnej listy i dodaj n kroków podjętych w celu scalenia dwóch wynikowych list). Forma zamknięta wynika z głównego twierdzenia o rekurencjach typu dziel i zwyciężaj .

Liczba porównań dokonanych przez sortowanie przez scalanie w najgorszym przypadku jest podana przez liczby sortujące . Liczby te są równe lub nieco mniejsze niż ( n ⌈ lg n ⌉ − 2 ^{⌈lg n ⌉} + 1), czyli pomiędzy ( n lg n − n + 1) a ( n lg n + n + O(lg n ) ). Najlepszy przypadek sortowania przez scalanie zajmuje o połowę mniej iteracji niż jego najgorszy przypadek.

Dla dużej liczby n i losowo uporządkowanej listy wejściowej, oczekiwana (średnia) liczba porównań w sortowaniu przez scalanie zbliża się do wartości α · n mniejszej niż najgorszy przypadek, gdzie ${\ Displaystyle \ alfa = -1 + \ suma _ {k = 0} ^ {\ infty} {\ Frac {1} {2 ^ {k} + 1}} \ około 0,2645.}$

W najgorszym przypadku sortowanie przez scalanie używa około 39% mniej porównań niż sortowanie szybkie w swoim przeciętnym przypadku, a pod względem ruchów, złożoność sortowania przez scalanie w najgorszym przypadku wynosi O ( n log n ) - taka sama złożoność jak w najlepszym przypadku sortowania szybkiego.

Sortowanie przez scalanie jest bardziej wydajne niż sortowanie szybkie w przypadku niektórych typów list, jeśli dane, które mają być sortowane, mogą być wydajnie dostępne tylko sekwencyjnie i dlatego jest popularne w językach takich jak Lisp , gdzie sekwencyjny dostęp do struktur danych jest bardzo powszechny. W przeciwieństwie do niektórych (efektywnych) implementacji szybkiego sortowania, sortowanie przez scalanie jest sortowaniem stabilnym.

Najczęstsza implementacja sortowania przez scalanie nie sortuje w miejscu; w związku z tym rozmiar pamięci wejścia musi być zaalokowany dla posortowanego wyjścia, które ma być przechowywane (patrz poniżej dla odmian, które wymagają tylko n /2 dodatkowych spacji).

Warianty

Warianty sortowania przez scalanie dotyczą przede wszystkim zmniejszenia złożoności przestrzeni i kosztów kopiowania.

Prostą alternatywą dla zmniejszenia narzutu przestrzeni do n /2 jest utrzymanie lewej i prawej strony jako połączonej struktury, skopiowanie tylko lewej części m do przestrzeni tymczasowej i nakierowanie procedury scalania na umieszczenie scalonego wyjścia w m . W tej wersji lepiej jest przydzielić tymczasową przestrzeń poza procedurą scalania , aby potrzebna była tylko jedna alokacja. Wspomniane wcześniej nadmierne kopiowanie jest również łagodzone, ponieważ ostatnia para wierszy przed instrukcją zwracania wyniku (funkcja merge w powyższym pseudokodzie) staje się zbyteczna.

Jedną z wad sortowania przez scalanie, gdy jest zaimplementowana na tablicach, jest jego wymagana pamięć robocza $O (n)$ . Zasugerowano kilka wariantów w miejscu :

Katajainena i in. przedstawić algorytm, który wymaga stałej ilości pamięci roboczej: wystarczającej ilości miejsca do przechowywania jednego elementu tablicy wejściowej i dodatkowej przestrzeni do przechowywania $O (1)$ wskaźników do tablicy wejściowej. Osiągają czas $O (n log n)$ związany z małymi stałymi, ale ich algorytm nie jest stabilny.
Podjęto kilka prób stworzenia lokalnego algorytmu scalania , który można łączyć ze standardowym sortowaniem scalającym (z góry na dół lub z dołu do góry), aby uzyskać sortowanie przez scalanie na miejscu. W tym przypadku pojęcie „w miejscu” może być złagodzone i oznacza „przyjmowanie logarytmicznego miejsca na stosie”, ponieważ standardowe sortowanie przez scalanie wymaga tej ilości miejsca do własnego wykorzystania stosu. Wykazali to Geffert i in. że w miejscu, stabilne łączenie jest możliwe w czasie $O (n log n)$ przy stałej ilości miejsca na zarysowania, ale ich algorytm jest skomplikowany i ma wysokie współczynniki stałe: łączenie tablic o długości $n$ i $m$ może zająć $5 n + 12 m + o (m)$ ruchy. Ten wysoki współczynnik stały i skomplikowany algorytm stały zostały uproszczone i łatwiejsze do zrozumienia. Bing-Chao Huang i Michael A. Langston przedstawili prosty liniowy algorytm czasu, praktyczny w celu scalania posortowanej listy przy użyciu stałej ilości dodatkowego miejsca. Obaj korzystali z prac Kronroda i innych. Łączy się w liniowy czas i stałą dodatkową przestrzeń. Algorytm zajmuje nieco więcej czasu niż standardowe algorytmy sortowania przez scalanie, które mogą wykorzystać O(n) tymczasowych dodatkowych komórek pamięci, mniej niż dwa razy. Chociaż algorytm jest znacznie szybszy w praktyce, ale jest niestabilny również dla niektórych list. Ale używając podobnych koncepcji, byli w stanie rozwiązać ten problem. Inne algorytmy w miejscu obejmują SymMerge, który zajmuje łącznie czas $O ((n + m) log (n + m))$ i jest stabilny. Włączenie takiego algorytmu do sortowania przez scalanie zwiększa jego złożoność do nieliniowego , ale wciąż quasilinearnego , $O (n ( log n) 2)$ .
Nowoczesnym stabilnym scalaniem liniowym i w miejscu jest sortowanie przez scalanie bloków .

Alternatywą dla ograniczenia kopiowania do wielu list jest powiązanie nowego pola informacji z każdym kluczem (elementy w m nazywane są kluczami). To pole będzie używane do łączenia kluczy i wszelkich powiązanych informacji na posortowanej liście (klucz i powiązane z nim informacje nazywane są rekordem). Następnie następuje scalanie posortowanych list poprzez zmianę wartości linków; w ogóle nie trzeba przenosić żadnych rekordów. Pole zawierające tylko łącze będzie zazwyczaj mniejsze niż cały rekord, więc zostanie również wykorzystane mniej miejsca. Jest to standardowa technika sortowania, która nie ogranicza się do sortowania przez scalanie.

Używaj z napędami taśmowymi

Algorytmy typu sortowania przez scalanie umożliwiły sortowanie dużych zbiorów danych na wczesnych komputerach, które według współczesnych standardów miały małe pamięci o dostępie swobodnym. Zapisy były przechowywane na taśmie magnetycznej i przetwarzane na bankach napędów taśm magnetycznych, takich jak IBM 729s .

Zewnętrzny seryjnej sortowania jest praktyczny uruchomić za pomocą dysku lub taśmy napędów, gdy dane mają być sortowane jest zbyt duża, aby zmieścić się w pamięci . Sortowanie zewnętrzne wyjaśnia, w jaki sposób sortowanie przez scalanie jest realizowane w napędach dysków. Typowe sortowanie z napędem taśmowym wykorzystuje cztery napędy taśmowe. Wszystkie operacje we/wy są sekwencyjne (z wyjątkiem przewijania na końcu każdego przebiegu). Minimalna implementacja może się obejść z zaledwie dwoma buforami rekordów i kilkoma zmiennymi programu.

Nazywając cztery napędy taśmowe jako A, B, C, D, z oryginalnymi danymi na A i używając tylko dwóch buforów zapisu, algorytm jest podobny do implementacji oddolnej , wykorzystującej pary napędów taśmowych zamiast tablic w pamięci. Podstawowy algorytm można opisać następująco:

Scal pary rekordów z A; pisanie dwurekordowych podlist na przemian do C i D.
Połącz podlisty z dwoma rekordami z C i D w podlisty z czterema rekordami; pisząc je na przemian do A i B.
Połącz podlisty z czterema rekordami z A i B w podlisty z ośmioma rekordami; zapisując je na przemian do C i D
Powtarzaj, aż będziesz mieć jedną listę zawierającą wszystkie dane, posortowane — w logu ₂ ( n ) przechodzi.

Zamiast zaczynać od bardzo krótkich przebiegów, zwykle używany jest algorytm hybrydowy , w którym początkowy przebieg odczytuje wiele rekordów do pamięci, wykonuje wewnętrzne sortowanie, aby utworzyć długi przebieg, a następnie rozdziela te długie przebiegi na zestaw wyjściowy. Ten krok pozwala uniknąć wielu wczesnych przejść. Na przykład wewnętrzny rodzaj 1024 rekordów pozwoli zapisać dziewięć przebiegów. Sortowanie wewnętrzne jest często duże, ponieważ ma taką zaletę. W rzeczywistości istnieją techniki, które mogą sprawić, że początkowe przebiegi będą dłuższe niż dostępna pamięć wewnętrzna. Jeden z nich, „pług śnieżny” Knutha (oparty na binarnym min-heap ), generuje przebiegi dwukrotnie dłuższe (średnio) niż rozmiar używanej pamięci.

Z pewnym obciążeniem powyższy algorytm można zmodyfikować tak, aby używał trzech taśm. Czas działania O ( n log n ) można również osiągnąć za pomocą dwóch kolejek lub stosu i kolejki lub trzech stosów. W innym kierunku, używając k > dwóch taśm (i elementów O ( k ) w pamięci), możemy zmniejszyć liczbę operacji na taśmie w O (log k ) razy, używając łączenia k/2 .

Bardziej wyrafinowanym sortowaniem przez scalanie, które optymalizuje użycie napędu taśmowego (i dysku), jest sortowanie przez scalanie wielofazowe .

Optymalizacja sortowania przez scalanie

Kafelkowe sortowanie przez scalanie zastosowane do tablicy losowych liczb całkowitych. Oś pozioma to indeks tablicy, a oś pionowa to liczba całkowita.

Na nowoczesnych komputerach lokalizacja odniesienia może mieć ogromne znaczenie w optymalizacji oprogramowania , ponieważ stosowane są wielopoziomowe hierarchie pamięci . Zaproponowano wersje algorytmu sortowania przez scalanie uwzględniające pamięć podręczną , których operacje zostały specjalnie dobrane tak, aby zminimalizować ruch stron do iz pamięci podręcznej maszyny. Na przykład Algorytm kafelkowego sortowania przez scalanie zatrzymuje partycjonowanie podtablic po osiągnięciu podtablic o rozmiarze S, gdzie S jest liczbą elementów danych mieszczących się w pamięci podręcznej procesora. Każda z tych podtablic jest sortowana za pomocą algorytmu sortowania w miejscu, takiego jaksortowanie przez wstawianie, aby zniechęcić do wymiany pamięci, a normalne sortowanie przez scalanie jest następnie wykonywane w standardowy sposób rekurencyjny. Algorytm ten wykazał lepszą wydajność na maszynach, które korzystają z optymalizacji pamięci podręcznej. (LaMarca i Ladner 1997)

Kronrod (1969) zasugerował alternatywną wersję sortowania przez scalanie, która wykorzystuje stałą dodatkową przestrzeń. Algorytm ten został później dopracowany. ( Katajainen, Pasanen i Teuhola 1996 )

Ponadto wiele zastosowań zewnętrznego sortowania wykorzystuje formę sortowania przez scalanie, w której dane wejściowe są dzielone na większą liczbę podlist, najlepiej na liczbę, dla której ich połączenie nadal sprawia, że aktualnie przetwarzany zestaw stron mieści się w pamięci głównej.

Sortowanie przez scalanie równoległe

Sortowanie przez scalanie jest dobrze zrównoleglone dzięki zastosowaniu metody dziel i zwyciężaj . Na przestrzeni lat opracowano kilka różnych równoległych wariantów algorytmu. Niektóre algorytmy równoległego sortowania przez scalanie są silnie powiązane z sekwencyjnym algorytmem łączenia odgórnego, podczas gdy inne mają inną ogólną strukturę i używają metody scalania K-way .

Sortowanie przez scalanie z rekurencją równoległą

Procedurę sortowania przez scalanie sekwencyjne można opisać w dwóch fazach, fazie dzielenia i fazie łączenia. Pierwsza składa się z wielu wywołań rekurencyjnych, które wielokrotnie wykonują ten sam proces dzielenia, dopóki podsekwencje nie zostaną posortowane w trywialny sposób (zawierające jeden lub żaden element). Intuicyjnym podejściem jest równoległość tych wywołań rekurencyjnych. Poniższy pseudokod opisuje sortowanie przez scalanie z rekurencją równoległą przy użyciu słów kluczowych fork i join :

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid := ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Ten algorytm jest trywialną modyfikacją wersji sekwencyjnej i nie jest dobrze zrównoleglony. Dlatego jego przyspieszenie nie jest imponujące. To ma rozpiętość od , który jest tylko poprawa w porównaniu do wersji sekwencyjnej (patrz Wprowadzenie do algorytmów ). Wynika to głównie z metody scalania sekwencyjnego, ponieważ jest to wąskie gardło równoległych wykonań. ${\ Displaystyle \ Theta (n)}$ ${\ Displaystyle \ Theta (\ log n)}$

Sortowanie przez scalanie z równoległym scalaniem

Lepszą równoległość można osiągnąć za pomocą algorytmu scalania równoległego . Cormen i in. przedstawić wariant binarny, który łączy dwie posortowane podsekwencje w jedną posortowaną sekwencję wyjściową.

W jednej z sekwencji (dłuższej o nierównej długości) wybierany jest element indeksu środkowego. Jego pozycja w drugiej sekwencji jest określona w taki sposób, że sekwencja ta pozostanie posortowana, jeśli ten element zostanie wstawiony w tej pozycji. Dzięki temu wiadomo, ile innych elementów z obu ciągów jest mniejszych i można obliczyć pozycję wybranego elementu w ciągu wyjściowym. Dla utworzonych w ten sposób sekwencji cząstkowych mniejszych i większych elementów algorytm scalania jest ponownie wykonywany równolegle aż do osiągnięcia przypadku bazowego rekurencji.

Poniższy pseudokod przedstawia zmodyfikowaną metodę sortowania przez scalanie równoległe przy użyciu algorytmu scalania równoległego (zapożyczonego z Cormen et al.).

/**
 * A: Input array
 * B: Output array
 * lo: lower bound
 * hi: upper bound
 * off: offset
 */
algorithm parallelMergesort(A, lo, hi, B, off) is
    len := hi - lo + 1
    if len == 1 then
        B[off] := A[lo]
    else let T[1..len] be a new array
        mid := ⌊(lo + hi) / 2⌋ 
        mid' := mid - lo + 1
        fork parallelMergesort(A, lo, mid, T, 1)
        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(T, 1, mid', mid' + 1, len, B, off)

Aby przeanalizować relację rekurencyjną dla najgorszego przypadku, wywołania rekurencyjne parallelMergesort muszą być włączone tylko raz ze względu na ich równoległe wykonanie, uzyskując

{\ Displaystyle T_ {\ infty} ^ {\ tekst {sortowanie}} (n) = T_ {\ infty} ^ {\ tekst {sortowanie}} \ lewo ({\ Frac {n} {2}} \ prawej) + T_{\infty }^{\text{scal}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \ lewo(\log(n)^{2}\prawo).}

Aby uzyskać szczegółowe informacje na temat złożoności procedury scalania równoległego, zobacz Algorytm scalania .

Rozwiązanie tego nawrotu podaje

{\ Displaystyle T_ {\ infty } ^ {\ tekst {sortowanie}} = \ Theta \ lewo (\ log (n) ^ {3} \ prawej).}

Ten algorytm łączenia równoległego osiąga równoległość , która jest znacznie wyższa niż równoległość poprzedniego algorytmu. Takie sortowanie może dobrze działać w praktyce w połączeniu z szybkim stabilnym sortowaniem sekwencyjnym, takim jak sortowanie przez wstawianie i szybkim scalaniem sekwencyjnym jako podstawowym przypadkiem scalania małych tablic. ${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$

Równoległe sortowanie przez scalanie wielostronne

Wydaje się arbitralne ograniczanie algorytmów sortowania przez scalanie do metody łączenia binarnego, ponieważ zazwyczaj dostępnych jest p > 2 procesorów. Lepszym podejściem może być użycie metody łączenia K-way , uogólnienia łączenia binarnego, w którym scalane są posortowane sekwencje. Ten wariant scalania dobrze nadaje się do opisania algorytmu sortowania w PRAM-ie . $k$

Podstawowy pomysł

Równoległy wielokierunkowy proces sortowania przez scalanie na czterech procesorach do .

t_{0}

t_{3}

Biorąc pod uwagę nieposortowaną sekwencję elementów, celem jest posortowanie sekwencji z dostępnymi procesorami . Elementy te są równomiernie rozłożone na wszystkie procesory i posortowane lokalnie przy użyciu sekwencyjnego algorytmu sortowania . Stąd sekwencja składa się z posortowanych sekwencji o długości . Dla uproszczenia niech będzie wielokrotnością , tak że dla . ${\ Displaystyle n}$ $p$ $S_{1},...,S_{p}$ ${\textstyle \lceil {\frac {n}{p}}\rceil }$ ${\ Displaystyle n}$ $p$ ${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$ $i=1,...,p$

Sekwencje te zostaną użyte do przeprowadzenia selekcji wielosekwencyjnej/wyboru rozdzielacza. Dla , algorytm określa elementy rozdzielające o randze globalnej . Następnie odpowiednie pozycje w każdej sekwencji są określane za pomocą wyszukiwania binarnego, a zatem są dalej dzielone na podsekwencje za pomocą . $j=1,...,p$ $v_{j}$ ${\textstyle k=j{\frac {n}{p}}}$ $v_{1},...,v_{p}$ $S_{i}$ $S_{i}$ $p$ $S_{i,1},...,S_{i,p}$ ${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$

Ponadto elementy z są przypisane do procesora , czyli wszystkich elementów pomiędzy rank i rank , które są rozłożone na all . W ten sposób każdy procesor otrzymuje sekwencję posortowanych sekwencji. Fakt, że ranga elementów rozdzielacza została wybrana globalnie, zapewnia dwie ważne właściwości: Z jednej strony wybrano tak, aby każdy procesor mógł nadal operować na elementach po przypisaniu. Algorytm jest doskonale zrównoważony . Z drugiej strony wszystkie elementy na procesorze są mniejsze lub równe wszystkim elementom na procesorze . W związku z tym każdy procesor wykonuje połączenie p- way lokalnie, a tym samym uzyskuje uporządkowaną sekwencję ze swoich podsekwencji. Ze względu na drugą właściwość, nie trzeba wykonywać dalszych p -way-merge, wyniki należy jedynie zebrać w kolejności według numeru procesora. $S_{1,i},...,S_{p,i}$ $i$ ${\textstyle (i-1){\frac {n}{p}}}$ ${\textstyle i{\frac {n}{p}}}$ $S_{i}$ $k$ $v_{i}$ $k$ ${\textstyle n/p}$ $i$ $i+1$

Wybór wielu sekwencji

W najprostszej postaci, mając posortowane sekwencje równomiernie rozłożone na procesorach i rank , zadaniem jest znalezienie elementu o globalnym rankingu w unii sekwencji. Stąd można to wykorzystać do podzielenia każdej na dwie części przy wskaźniku rozdzielacza , gdzie dolna część zawiera tylko elementy mniejsze niż , a elementy większe niż znajdują się w górnej części. $p$ $S_{1},...,S_{p}$ $p$ $k$ $x$ $k$ $S_{i}$ $l_{i}$ $x$ $x$

Przedstawiony algorytm sekwencyjny zwraca indeksy podziałów w każdym ciągu, np. indeksy w ciągach takich, które mają globalną rangę mniejszą niż i . $l_{i}$ $S_{i}$ ${\ Displaystyle S_ {i} [l_ {i}]}$ $k$ ${\ Displaystyle \ operatorname {ranga} \ po lewej (S_ {i} [l_ {i} +1] \ po prawej) \ geq k}$

algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) is
    for i = 1 to p do 
	(l_i, r_i) = (0, |S_i|-1)
	
    while there exists i: l_i < r_i do
	// pick Pivot Element in S_j[l_j], .., S_j[r_j], chose random j uniformly
	v := pickPivot(S, l, r)
	for i = 1 to p do 
	    m_i = binarySearch(v, S_i[l_i, r_i]) // sequentially
	if m_1 + ... + m_p >= k then // m_1+ ... + m_p is the global rank of v
	    r := m  // vector assignment
	else
	    l := m 
	
    return l

Do analizy złożoności wybierany jest model PRAM . Jeśli dane są równomiernie rozłożone na wszystkich , wykonanie p-fold metody binarySearch ma czas działania . Oczekiwana głębokość rekurencji jest taka sama jak w zwykłym Quickselect . Zatem całkowity oczekiwany czas pracy wynosi . $p$ ${\ Displaystyle {\ mathcal {O}} \ po lewej (p \ log \ po lewej (n / p \ po prawej) \ po prawej)}$ ${\ Displaystyle {\ mathcal {O}} \ lewo (\ log \ lewo (\ textstyle \ suma _ {i} | S_ {i} | \ prawej) \ prawej) = {\ mathcal {O}} (\ log ( n))}$ ${\ Displaystyle {\ mathcal {O}} \ lewo (p \ log (n / p) \ log (n) \ prawo)}$

Zastosowany w równoległym sortowaniu przez scalanie wielostronne, algorytm ten musi być wywoływany równolegle, tak aby wszystkie elementy rozdzielające rangi for zostały znalezione jednocześnie. Te elementy rozdzielające mogą być następnie użyte do podzielenia każdej sekwencji na części, z takim samym całkowitym czasem działania wynoszącym . ${\textstyle i{\frac {n}{p}}}$ $i=1,..,p$ $p$ ${\ Displaystyle {\ mathcal {O}} \ lewo (p \, \ log (n/p) \ log (n) \ prawo)}$

Pseudo kod

Poniżej podano pełny pseudokod równoległego algorytmu sortowania przez scalanie wieloetapowe. Zakładamy, że istnieje synchronizacja bariery przed i po wyborze wielosekwencyjnym, tak że każdy procesor może prawidłowo określić elementy rozdzielające i podział sekwencji.

/**
 * d: Unsorted Array of Elements
 * n: Number of Elements
 * p: Number of Processors
 * return Sorted Array
 */
algorithm parallelMultiwayMergesort(d : Array, n : int, p : int) is
    o := new Array[0, n]                         // the output array
    for i = 1 to p do in parallel                // each processor in parallel
        S_i := d[(i-1) * n/p, i * n/p] 	         // Sequence of length n/p
	sort(S_i)                                // sort locally
        synch
	v_i := msSelect([S_1,...,S_p], i * n/p)          // element with global rank i * n/p
        synch
	(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // split s_i into subsequences
	    
	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // merge and assign to output array
	
    return o

Analiza

Po pierwsze, każdy procesor sortuje przypisane elementy lokalnie za pomocą algorytmu sortowania o złożoności . Następnie elementy rozgałęźnika muszą zostać obliczone w czasie . Wreszcie, każda grupa podziałów musi być łączona równolegle przez każdy procesor z czasem działania przy użyciu sekwencyjnego algorytmu łączenia p-way . Tak więc całkowity czas działania jest podany przez $n/p$ ${\ Displaystyle {\ mathcal {O}} \ lewo (n / p \; \ log (n / p) \ prawo)}$ ${\ Displaystyle {\ mathcal {O}} \ lewo (p \, \ log (n/p) \ log (n) \ prawo)}$ $p$ ${\mathcal {O}}(\log(p)\;n/p)$

${\ Displaystyle {\ mathcal {O}} \ lewo ({\ Frac {n} {p}} \ log \ lewo ({\ Frac {n} {p}} \ prawej) + p \ log \ lewo ({\ frac {n}{p}}\prawo)\log(n)+{\frac {n}{p}}\log(p)\prawo)}$ .

Praktyczna adaptacja i zastosowanie

Algorytm sortowania przez scalanie wielokierunkowe jest bardzo skalowalny dzięki wysokiej zdolności zrównoleglania, co pozwala na użycie wielu procesorów. To sprawia, że algorytm jest realnym kandydatem do sortowania dużych ilości danych, takich jak te przetwarzane w klastrach komputerowych . Ponadto, ponieważ w takich systemach pamięć zwykle nie jest zasobem ograniczającym, wada złożoności przestrzennej sortowania przez scalanie jest znikoma. Jednak w takich systemach ważne stają się inne czynniki, które nie są brane pod uwagę podczas modelowania na PRAM-ie . W tym przypadku należy wziąć pod uwagę następujące aspekty: Hierarchia pamięci , gdy dane nie mieszczą się w pamięci podręcznej procesorów, lub narzut komunikacji związany z wymianą danych między procesorami, który może stać się wąskim gardłem, gdy dane nie są już dostępne za pośrednictwem współdzielonej pamięć.

Sanders i in. przedstawili w swoim artykule masowy synchroniczny algorytm równoległy dla wielopoziomowego wielokierunkowego sortowania łączenia, który dzieli procesory na grupy wielkości . Wszystkie procesory najpierw sortują lokalnie. W przeciwieństwie do jednopoziomowego sortowania wielokierunkowego, sekwencje te są następnie dzielone na części i przypisywane do odpowiednich grup procesorów. Te kroki są powtarzane rekurencyjnie w tych grupach. Zmniejsza to komunikację, a zwłaszcza pozwala uniknąć problemów z wieloma małymi wiadomościami. Hierarchiczna struktura podstawowej sieci rzeczywistej może być wykorzystana do zdefiniowania grup procesorów (np. racki , klastry ,...). $p$ ${\ Displaystyle r}$ $p'$ ${\ Displaystyle r}$

Dalsze warianty

Sortowanie przez scalanie było jednym z pierwszych algorytmów sortowania, w którym osiągnięto optymalne przyspieszenie, a Richard Cole użył sprytnego algorytmu podpróbkowania, aby zapewnić połączenie O (1). Inne zaawansowane algorytmy sortowania równoległego mogą osiągnąć takie same lub lepsze granice czasowe przy niższej stałej. Na przykład w 1991 roku David Powers opisał zrównoleglone szybkie sortowanie (i pokrewne sortowanie radix ), które może działać w czasie O (log n ) na równoległej maszynie o dostępie swobodnym (PRAM) CRCW z n procesorami, wykonując niejawne partycjonowanie. Powers pokazuje dalej, że potokowa wersja Bitonic Mergesort Batchera w czasie O ((log n ) ² ) w sieci sortowania motyli jest w praktyce szybsza niż sortowanie O (log n ) w PRAM-ie, i przedstawia szczegółową dyskusję na temat ukryte koszty ogólne w porównaniu, podstawa i sortowanie równoległe.

Porównanie z innymi algorytmami sortowania

Chociaż sortowanie przez stertę ma takie same ograniczenia czasowe jak sortowanie przez scalanie, wymaga tylko Θ(1) przestrzeni pomocniczej zamiast Θ( n ) sortowania przez scalanie . W typowych nowoczesnych architekturach wydajne implementacje szybkiego sortowania generalnie przewyższają sortowanie przez scalanie w przypadku sortowania tablic opartych na pamięci RAM. Z drugiej strony sortowanie przez scalanie jest sortowaniem stabilnym i jest bardziej wydajne w obsłudze nośników sekwencyjnych o wolnym dostępie. Sortowanie przez scalanie jest często najlepszym wyborem do sortowania połączonej listy : w tej sytuacji stosunkowo łatwo jest zaimplementować sortowanie przez scalanie w taki sposób, że wymaga tylko Θ(1) dodatkowej przestrzeni i powolnej wydajności losowego dostępu połączonej listy list sprawia, że niektóre inne algorytmy (takie jak quicksort) działają słabo, a inne (takie jak sortowanie sterty) są całkowicie niemożliwe.

Od wersji Perl 5.8 sortowanie przez scalanie jest domyślnym algorytmem sortowania (w poprzednich wersjach Perla było to sortowanie quicksort). W Javie metody Arrays.sort() używają sortowania przez scalanie lub dostrojonego szybkiego sortowania w zależności od typów danych, a w celu zwiększenia wydajności implementacji przełączają się na sortowanie przez wstawianie, gdy sortowanych jest mniej niż siedem elementów tablicy. Na Linuksa używa jądra scalania sortowania dla swoich powiązanych list. Python używa Timsort , innej dostrojonej hybrydy sortowania przez scalanie i sortowania przez wstawianie, które stało się standardowym algorytmem sortowania w Java SE 7 (dla tablic typów nieprymitywnych), na platformie Android oraz w GNU Octave .

Uwagi

Bibliografia

Cormen, Thomas H .; Leiserson, Charles E. ; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Wprowadzenie do algorytmów (3rd ed.). MIT Press i McGraw-Hill. Numer ISBN 0-262-03384-4.
Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Praktyczne sortowanie scalone w miejscu" . Nordic Journal of Computing . 3 (1): 27-40. CiteSeerX 10.1.1.22.8523 . ISSN 1236-6064 . Zarchiwizowane od oryginału w dniu 2011-08-07 . Pobrano 2009-04-04 .. Również praktyczne sortowanie na miejscu . Również [3]
Knut, Donald (1998). „Sekcja 5.2.4: Sortowanie przez scalanie”. Sortowanie i wyszukiwanie . Sztuka programowania komputerowego . 3 (wyd. 2). Addisona-Wesleya. s. 158–168. Numer ISBN 0-201-89685-0.
Kronrod, MA (1969). „Optymalny algorytm porządkowania bez pola operacyjnego”. Matematyka radziecka - Dokłady . 10 : 744.
LaMarca, A.; Ladner, RE (1997). „Wpływ pamięci podręcznych na wydajność sortowania”. Proc. 8 Ann. ACM-SIAM Symp. O algorytmach dyskretnych (SODA97) : 370–379. CiteSeerX 10.1.1.31.1153 .
Skiena, Steven S. (2008). „4.5: Sortowanie przez scalanie: Sortowanie według Dziel i zwyciężaj”. Podręcznik projektowania algorytmów (wyd. 2). Skoczek. s. 120-125. Numer ISBN 978-1-84800-069-8.
Mikrosystemy słoneczne. „Interfejs API tablic (Java SE 6)” . Źródło 2007-11-19 .
Oracle Corp. „Macierze (Java SE 10 i JDK 10)” . Pobrano 23.07.2018 .

Zewnętrzne linki

Animowane algorytmy sortowania: Merge Sort at the Wayback Machine (archiwum 6 marca 2015) – demonstracja graficzna
Otwarte struktury danych - Sekcja 11.1.1 - Sortowanie przez scalanie , Pat Morin

Languages

In other projects

Sortowanie scalające — Merge sort

Zawartość

Algorytm

Implementacja odgórna

Wdrażanie oddolne

Implementacja odgórna z wykorzystaniem list

Implementacja oddolna z wykorzystaniem list

Naturalne sortowanie przez scalanie

Analiza

Warianty

Używaj z napędami taśmowymi

Optymalizacja sortowania przez scalanie

Sortowanie przez scalanie równoległe

Sortowanie przez scalanie z rekurencją równoległą

Sortowanie przez scalanie z równoległym scalaniem

Równoległe sortowanie przez scalanie wielostronne

Podstawowy pomysł

Wybór wielu sekwencji

Pseudo kod

Analiza

Praktyczna adaptacja i zastosowanie

Dalsze warianty

Porównanie z innymi algorytmami sortowania

Uwagi

Bibliografia

Zewnętrzne linki