Merge Sort đa luồng (Multithreading) trong C++

Sắp xếp mảng số nguyên bằng thuật toán Merge Song song (Parallel Merge Sort) sử dụng đa luồng (pthread) trong C++.

Merge Sort

Thuật toán chia để trị: chia mảng thành 2 nửa, sắp xếp đệ quy từng nửa, sau đó gộp (merge) 2 nửa đã sắp xếp.

Đa luồng (Multithreading)

Thread là tiến trình nhẹ chia sẻ tài nguyên. Đa luồng cho phép chạy nhiều thread song song trên cùng một bộ xử lý, tận dụng đa lõi.

Ví dụ

Input: {3, 2, 1, 10, 8, 5, 7, 9, 4} Output: 1, 2, 3, 4, 5, 7, 8, 9, 10

Cách tiếp cận

1. Tạo mảng ngẫu nhiên.
2. Chia mảng thành 4 phần bằng nhau (với 4 thread).
3. Mỗi thread sắp xếp phần của mình bằng Merge Sort tuần tự.
4. Gộp 4 phần đã sắp xếp thành 2 phần, rồi gộp thành mảng hoàn chỉnh.

Mã nguồn C++ (pthread)

#include <iostream>
#include <pthread.h>
#include <time.h>
#define SIZE 20
#define THREAD_SIZE 4

using namespace std;

int arr[SIZE];
int temp_val = 0;

void combine_array(int first, int mid, int end) {
    int *left = new int[mid - first + 1];
    int *right = new int[end - mid];
    int n1 = mid - first + 1, n2 = end - mid;
    for (int i = 0; i < n1; i++) left[i] = arr[first + i];
    for (int i = 0; i < n2; i++) right[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = first;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) arr[k++] = left[i++];
        else arr[k++] = right[j++];
    }
    while (i < n1) arr[k++] = left[i++];
    while (j < n2) arr[k++] = right[j++];
}

void merge_sort_seq(int first, int end) {
    if (first < end) {
        int mid = first + (end - first) / 2;
        merge_sort_seq(first, mid);
        merge_sort_seq(mid + 1, end);
        combine_array(first, mid, end);
    }
}

void* merge_sort_thread(void* arg) {
    int set_val = temp_val++;
    int first = set_val * (SIZE / 4);
    int end = (set_val + 1) * (SIZE / 4) - 1;
    int mid = first + (end - first) / 2;
    if (first < end) {
        merge_sort_seq(first, mid);
        merge_sort_seq(mid + 1, end);
        combine_array(first, mid, end);
    }
    return nullptr;
}

int main() {
    srand(time(0));
    for (int i = 0; i < SIZE; i++) arr[i] = rand() % 100;

    pthread_t threads[THREAD_SIZE];
    for (int i = 0; i < THREAD_SIZE; i++)
        pthread_create(&threads[i], nullptr, merge_sort_thread, nullptr);
    for (int i = 0; i < THREAD_SIZE; i++)
        pthread_join(threads[i], nullptr);

    combine_array(0, (SIZE/2 - 1)/2, SIZE/2 - 1);
    combine_array(SIZE/2, SIZE/2 + (SIZE-1-SIZE/2)/2, SIZE - 1);
    combine_array(0, (SIZE - 1)/2, SIZE - 1);

    cout << "Merge Sort đa luồng: ";
    for (int i = 0; i < SIZE; i++) cout << arr[i] << " ";
    return 0;
}

Kết quả

Merge Sort đa luồng: 15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93

Kết luận

Bài viết trình bày Merge Sort song song bằng pthread trong C++. Chia mảng cho các thread sắp xếp độc lập, sau đó gộp dần. Tận dụng đa lõi CPU để tăng tốc. Lưu ý: pthread chỉ khả dụng trên Linux/Unix; Windows cần dùng std::thread (C++11) hoặc Windows API.