归并排序

定义

归并排序是一种基于比较和分治策略的稳定排序算法。原理是不断对数组进行划分和合并。时间复杂度为 O(nlogn)，空间复杂度为O(n)。

划分

void MergeSort(int* a, const int left, const int right)  
{  
    if (left >= right)  
       return; // 长度为 1 时停止划分  
    const int mid = left + (right - left) >> 1; // mid = (left + right) / 2;  
    MergeSort(a, left, mid); // 递归排序左半部分  
    MergeSort(a, mid + 1, right); // 递归排序右半部分  
    Merge(a, left, mid, right); // 合并  
}

合并

void Merge(int* a, const int left, const int mid, const int right)  
{  
    const int size = right - left + 1;  
    int temp[size]; // 临时数组，用于存放合并结果  
    int i = left, j = mid + 1, k = 0; // i, j 分别指向左右部分的起始位置  
    while (i <= mid && j <= right) // 左右都有元素时进行比较  
       temp[k++] = a[i] < a[j] ? a[i++] : a[j++]; // 选择小的元素  
    while (i <= mid) // 将左边剩余的元素添加到临时数组  
       temp[k++] = a[i++];  
    while (j <= right) // 将右边剩余的元素添加到临时数组  
       temp[k++] = a[j++];  
    for (k = 0; k < size; k++)  
       a[left + k] = temp[k]; // 将临时数组的元素复制回原数组  
}

模版

void Merge(int* a, const int left, const int mid, const int right)  
{  
    const int size = right - left + 1;  
    int temp[size]; // 临时数组，用于存放合并结果  
    int i = left, j = mid + 1, k = 0; // i, j 分别指向左右部分的起始位置  
    while (i <= mid && j <= right) // 左右都有元素时进行比较  
       temp[k++] = a[i] < a[j] ? a[i++] : a[j++]; // 选择小的元素  
    while (i <= mid) // 将左边剩余的元素添加到临时数组  
       temp[k++] = a[i++];  
    while (j <= right) // 将右边剩余的元素添加到临时数组  
       temp[k++] = a[j++];  
    for (k = 0; k < size; k++)  
       a[left + k] = temp[k]; // 将临时数组的元素复制回原数组  
}  
void MergeSort(int* a, const int left, const int right)  
{  
    if (left >= right)  
       return; // 长度为 1 时停止划分  
    const int mid = left + (right - left >> 1); // mid = (left + right) / 2;  
    MergeSort(a, left, mid); // 递归排序左半部分  
    MergeSort(a, mid + 1, right); // 递归排序右半部分  
    Merge(a, left, mid, right); // 合并  
}