Sortieralgorithmen: Merge sort

Der Merge sort ist ein weiteres Sortierverfahren, welches auf dem divide and conquer aufbaut. Genauso wie der Quick sort wird die zu sortierende Liste zunächst in mehrere Teillisten aufgeteilt. Anders als beim Quick sort gibt es hier aber kein Pivotelement, wonach eine Liste geteilt wird.
Die Listen werden immer in der Mitte aufgeteilt, sodass beide Teillisten gleich viele Elemente haben. Sollte eine gleichgroße Teilung nicht möglich sein, wenn eine Liste z.B. 5 Elemente hat, so wird entweder die linke oder die rechte Teilliste ein Element mehr haben, je nach Implementierung.

Wenn alle Teillisten sortiert sind, so werden diese miteinander verschmolzen, daher der Name merge. Beim Quick sort liegt der Schwerpunkt beim teilen der Listen mithilfe eines Pivotelements, welches immer ermittelt werden muss. Beim Merge sort dagegen werden die Teillisten rekursiv miteinander verschmolzen.

• Merge sort (c++)

#include <iostream>

void merge(int list[], unsigned int left, unsigned int split, unsigned int right) {
    unsigned int i, j, k;
    unsigned int subOne = split - left + 1;
    unsigned int subTwo =  right - split;

    /* create temp sub-arrays */
    int L[subOne], R[subTwo];

    /* Copy the elements to the sub-arrays */
    for(i = 0; i < subOne; i++){
        L[i] = list[left + i];
    }

    for(j = 0; j < subTwo; j++){
        R[j] = list[split + 1+ j];
    }

    /* Merge the sub-arrays back into the original array */
    i = 0; // Initial index of first sub-array
    j = 0; // Initial index of second sub-array
    k = left; // Initial index of merged sub-array
    while (i < subOne && j < subTwo) {
        if (L[i] <= R[j]) {
            list[k] = L[i];
            i++;
        } else {
            list[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of the left sub-array, if there are any */
    while (i < subOne) {
        list[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of the right sub-array, if there are any */
    while (j < subTwo) {
        list[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int list[], unsigned int left, unsigned int right) {
    if (left < right) {
        /* splitelement */
        unsigned int split = left + (right - left)/2;

        /* Sort left and right sub-array */
        mergeSort(list, left, split);
        mergeSort(list, split+1, right);

        merge(list, left, split, right);
    }
}

int main(){
    const unsigned int SIZE = 10;
    int list[SIZE] = {5,3,8,1,12,6,7,11,3,2};
    mergeSort(list,0,SIZE-1);
    
    for(unsigned int res = 0; res < SIZE; res++){
        std::cout << list[res] << "\n";
    }
    
    return 0;
}

Quelle
https://algs4.cs.princeton.edu/lectures/22Mergesort.pdf [letzter Zugriff: 07.02.2020, 19:00]