面试题：C语言并行化归并排序

并行化思路

数据划分：将待排序数组划分成多个子数组，每个子数组由一个线程或OpenMP线程块独立处理。这样可以充分利用多核处理器的并行计算能力。
局部排序：每个线程对分配给自己的子数组进行独立排序，例如使用串行的归并排序算法对局部子数组排序。
归并合并：将各个已排序的子数组合并成一个完整的有序数组。这一步可以采用并行归并的方式，多个线程同时处理不同部分的合并操作。

关键代码片段（OpenMP示例）

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

// 合并两个子数组
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 串行归并排序
void serialMergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        serialMergeSort(arr, l, m);
        serialMergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

// 并行归并排序
void parallelMergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        #pragma omp parallel sections
        {
            #pragma omp section
            parallelMergeSort(arr, l, m);
            #pragma omp section
            parallelMergeSort(arr, m + 1, r);
        }

        merge(arr, l, m, r);
    }
}

性能提升分析

理论加速比：根据Amdahl定律，加速比 $S = \frac{1}{(1 - p)+\frac{p}{n}}$，其中 $p$ 是可并行化部分的比例，$n$ 是处理器核心数。对于归并排序，数据划分和局部排序部分可高度并行，假设这部分占总计算量的比例很高（接近1），随着核心数 $n$ 的增加，加速比会接近 $n$。
实际性能：在实际多核环境中，并行化归并排序确实能显著提升性能。但实际加速比可能受限于任务调度开销、缓存一致性问题以及数据依赖。例如，任务调度开销会随着线程数增加而增加，如果任务划分不合理，部分线程可能会处于等待状态，降低整体效率。缓存一致性问题会导致处理器之间的数据同步开销，影响性能提升。然而，通过合理的数据划分和任务调度，并行化归并排序能有效利用多核资源，在大规模数据排序时展现出明显的性能优势。

星途面试题库

面试题：C语言并行化归并排序

知识考点

面试题答案

并行化思路

关键代码片段（OpenMP示例）

性能提升分析