Paralleles Merge-Sort in C++: Effiziente Datenverarbeitung mit Threads

Einleitung: Warum paralleles Sortieren?

In der heutigen datengetriebenen Welt – von KI-Modellen bis hin zu Echtzeit-Analysen in Finanz-Apps – ist effizientes Sortieren unerlässlich. Der sequentielle Merge-Sort ist zwar zuverlässig, aber bei großen Datenmengen (z. B. 100.000 Elemente) wird die Grenze der Rechenleistung schnell erreicht. Hier kommt die parallele Datenverarbeitung ins Spiel: Durch Aufteilung der Arbeit auf mehrere Threads kann die Sortierzeit drastisch reduziert werden. In diesem Tutorial zeigen wir dir, wie du einen sequentiellen Merge-Sort in C++ parallelisierst – genau wie in der CSCN73000 Assignment 2 gefordert.

Grundlagen: Merge-Sort verstehen

Merge-Sort basiert auf dem Divide-and-Conquer-Prinzip: Die Liste wird rekursiv in zwei Hälften geteilt, bis nur noch ein Element übrig ist, dann werden die Hälften sortiert zusammengeführt. Die Zeitkomplexität beträgt O(n log n). Der sequentielle Code sieht typischerweise so aus:

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Der Flaschenhals ist die Rekursion: Jeder Aufruf wartet, bis die beiden Hälften fertig sind. Genau hier setzt die Parallelisierung an.

Paralleles Merge-Sort mit C++ Threads

Um den Algorithmus zu parallelisieren, erstellen wir eine neue Funktion Parallel_Merge_Sort, die die Daten in Teile zerlegt und diese auf mehrere Threads verteilt. Dabei müssen wir kritische Abschnitte schützen – z. B. das Zusammenführen der Teilergebnisse. Ein einfacher Ansatz ist die Verwendung von std::thread aus C++11. Hier ein Grundgerüst:

#include <thread>
#include <vector>

void parallel_merge_sort(int arr[], int left, int right, int depth) {
    if (depth <= 0 || left >= right) {
        merge_sort(arr, left, right); // sequentiell für kleine Teile
        return;
    }
    int mid = left + (right - left) / 2;
    std::thread t1(parallel_merge_sort, arr, left, mid, depth - 1);
    std::thread t2(parallel_merge_sort, arr, mid + 1, right, depth - 1);
    t1.join();
    t2.join();
    merge(arr, left, mid, right);
}

Die Tiefe (depth) steuert, wie viele Threads erstellt werden – typischerweise 2^(depth) Threads. Für N=100.000 reichen oft 4–8 Threads.

Performance-Messung und Optimierung

Um die Effizienz zu vergleichen, messen wir die Ausführungszeit beider Versionen mit std::chrono. Wichtig: Array-Ausgaben auskommentieren und N auf 100.000 oder mehr erhöhen. Ein Beispiel:

auto start = std::chrono::high_resolution_clock::now();
merge_sort(arr, 0, N-1);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> seq_time = end - start;

start = std::chrono::high_resolution_clock::now();
parallel_merge_sort(arr, 0, N-1, 2); // 4 Threads
end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> par_time = end - start;

std::cout << "Sequentiell: " << seq_time.count() << "s
";
std::cout << "Parallel: " << par_time.count() << "s
";
std::cout << "Speedup: " << seq_time / par_time << "x
";

Erwartetes Ergebnis: Die parallele Version ist deutlich schneller – je nach Hardware 2- bis 4-fach.

Kritische Abschnitte und Thread-IDs

Ein kritischer Abschnitt ist der Merge-Vorgang, da mehrere Threads gleichzeitig auf das Array zugreifen könnten. Um Konflikte zu vermeiden, verwenden wir einen Mutex. Zusätzlich soll ein globaler Vektor die Thread-IDs sammeln, die den kritischen Abschnitt betreten:

std::vector<std::thread::id> thread_ids;
std::mutex mtx;

void merge(int arr[], int left, int mid, int right) {
    std::lock_guard<std::mutex> lock(mtx);
    thread_ids.push_back(std::this_thread::get_id());
    // ... Merge-Logik ...
}

Nach der Ausführung kannst du die Anzahl der beteiligten Threads ausgeben – ein schöner Einblick in die Parallelarbeit.

Trend-Beispiel: Wie ein Gaming-Turnier

Stell dir vor, du organisierst ein E-Sports-Turnier mit 100.000 Spielern. Statt alle Spiele nacheinander auszutragen (sequentiell), teilst du die Spieler in 8 Gruppen auf und lässt jede Gruppe parallel spielen. Die Gruppensieger werden dann in einem finalen Turnierbaum zusammengeführt. Genau so funktioniert paralleles Merge-Sort: Die Arbeit wird aufgeteilt, parallel bearbeitet und am Ende zusammengeführt. Das spart Zeit – und in der Welt von KI-Training oder Big-Data-Analysen kann das über Erfolg oder Misserfolg entscheiden.

Fazit

Paralleles Merge-Sort ist ein klassisches Beispiel für die Leistungsfähigkeit von Multithreading. Mit C++-Threads und einem durchdachten Design kannst du die Sortierzeit drastisch reduzieren. Die CSCN73000 Assignment 2 fordert genau diese Umsetzung – inklusive Performance-Messung und Dokumentation der Thread-IDs. Probiere es selbst aus: Starte mit N=10, steigere auf 100.000 und beobachte den Speedup. Viel Erfolg!