归并排序

归并排序（Merge Sort）

归并排序算法采用分治法：

分解：将序列每次折半划分。
合并：将划分后的序列两两按序合并。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

归并排序每次将数组折半对分，一共分了 $logn$ 次，每一层进行合并操作的运算量是n，所以时间复杂度为 $O(nlogn)$ 。归并排序与快速排序的实际速度取决于输入数据和具体实现，不能一概而论。

时间复杂度	空间复杂度	稳定性	设计思想
$O(nlogn)$	$O(n)$	稳定	分治法

归并排序

#include <stdio.h>
#include <string.h>

#define min(a, b) ((a) < (b) ? (a) : (b))

typedef int T;

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

/**
 * Merge Sort (original v1.0)
 */
T *merge_sort(T *arr, int n) {
    if (n <= 1) {
        return arr;
    }

    int mid = n / 2;
    T left_half[mid];
    T right_half[n - mid];
    memcpy(left_half, arr, mid * sizeof(T));
    memcpy(right_half, arr + mid, (n - mid) * sizeof(T));

    merge_sort(left_half, mid);
    merge_sort(right_half, n - mid);

    int i = 0;
    int j = 0;
    int k = 0;

    while (i < mid && j < n - mid) {
        if (left_half[i] <= right_half[j]) {
            arr[k] = left_half[i];
            i++;
        } else {
            arr[k] = right_half[j];
            j++;
        }
        k++;
    }

    while (i < mid) {
        arr[k] = left_half[i];
        i++;
        k++;
    }

    while (j < n - mid) {
        arr[k] = right_half[j];
        j++;
        k++;
    }

    return arr;
}

int main() {
    int arr[] = {39, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    merge_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

相等时优先取左侧元素，才能保留原有相对顺序；示例中的比较条件已由 < 修正为 <=。

归并排序优化

简单的归并排序利用分治法，递归地对小规模子数组进行处理。但是递归会使小规模问题中方法调用太过频繁，因此对于规模较小的子数组可以采用插入排序。一般来说插入排序在小数组中比归并更快，这种优化在一些实现和测试中可以使归并排序的运行时间缩短10% $\sim$ 15%，具体收益取决于数据、阈值和运行环境。

另一个可以优化的地方是对于单次合并的过程，例如将子数组 $arr[start..mid]$ 和 $arr[mid+1..end]$ 进行合并，如果 $arr[mid] \le arr[mid+1]$ 的话，说明 $arr[start..end]$ 已经为有序状态，无需再进行不必要的合并。

归并排序优化

#include <stdio.h>
#include <string.h>

#define min(a, b) ((a) < (b) ? (a) : (b))

typedef int T;

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

/**
 * Merge Sort (original v1.0)
 */
T *merge_sort(T *arr, int n) {
    if (n <= INSERTION_SORT_THRESHOLD) {
        return insertion_sort(arr, n);
    }

    int mid = n / 2;
    T left_half[mid];
    T right_half[n - mid];
    memcpy(left_half, arr, mid * sizeof(T));
    memcpy(right_half, arr + mid, (n - mid) * sizeof(T));

    merge_sort(left_half, mid);
    merge_sort(right_half, n - mid);

    int i = 0;
    int j = 0;
    int k = 0;

    while (i < mid && j < n - mid) {
        if (left_half[i] <= right_half[j]) {
            arr[k] = left_half[i];
            i++;
        } else {
            arr[k] = right_half[j];
            j++;
        }
        k++;
    }

    while (i < mid) {
        arr[k] = left_half[i];
        i++;
        k++;
    }

    while (j < n - mid) {
        arr[k] = right_half[j];
        j++;
        k++;
    }

    return arr;
}

int main() {
    int arr[] = {39, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    merge_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

题目

归并时，左右两侧的队首元素都是6，稳定实现应该先取谁？

题目

已排序的左右区间分别为[1,3]和[4,8]，怎样避免不必要的合并？

对[8,3,7,2,5]按示例代码floor(n/2)拆分。画出整棵递归树；每次合并写出左右队首的比较、选择次序与写回结果。每个单元素区间无需继续拆分。

归并排序

归并排序（Merge Sort）

归并排序算法采用分治法：

分解：将序列每次折半划分。
合并：将划分后的序列两两按序合并。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

时间复杂度	空间复杂度	稳定性	设计思想
$O(nlogn)$	$O(n)$	稳定	分治法

归并排序

#include <stdio.h>
#include <string.h>

#define min(a, b) ((a) < (b) ? (a) : (b))

typedef int T;

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

/**
 * Merge Sort (original v1.0)
 */
T *merge_sort(T *arr, int n) {
    if (n <= 1) {
        return arr;
    }

    int mid = n / 2;
    T left_half[mid];
    T right_half[n - mid];
    memcpy(left_half, arr, mid * sizeof(T));
    memcpy(right_half, arr + mid, (n - mid) * sizeof(T));

    merge_sort(left_half, mid);
    merge_sort(right_half, n - mid);

    int i = 0;
    int j = 0;
    int k = 0;

    while (i < mid && j < n - mid) {
        if (left_half[i] <= right_half[j]) {
            arr[k] = left_half[i];
            i++;
        } else {
            arr[k] = right_half[j];
            j++;
        }
        k++;
    }

    while (i < mid) {
        arr[k] = left_half[i];
        i++;
        k++;
    }

    while (j < n - mid) {
        arr[k] = right_half[j];
        j++;
        k++;
    }

    return arr;
}

int main() {
    int arr[] = {39, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    merge_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

相等时优先取左侧元素，才能保留原有相对顺序；示例中的比较条件已由 < 修正为 <=。

归并排序优化

归并排序优化

#include <stdio.h>
#include <string.h>

#define min(a, b) ((a) < (b) ? (a) : (b))

typedef int T;

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

/**
 * Merge Sort (original v1.0)
 */
T *merge_sort(T *arr, int n) {
    if (n <= INSERTION_SORT_THRESHOLD) {
        return insertion_sort(arr, n);
    }

    int mid = n / 2;
    T left_half[mid];
    T right_half[n - mid];
    memcpy(left_half, arr, mid * sizeof(T));
    memcpy(right_half, arr + mid, (n - mid) * sizeof(T));

    merge_sort(left_half, mid);
    merge_sort(right_half, n - mid);

    int i = 0;
    int j = 0;
    int k = 0;

    while (i < mid && j < n - mid) {
        if (left_half[i] <= right_half[j]) {
            arr[k] = left_half[i];
            i++;
        } else {
            arr[k] = right_half[j];
            j++;
        }
        k++;
    }

    while (i < mid) {
        arr[k] = left_half[i];
        i++;
        k++;
    }

    while (j < n - mid) {
        arr[k] = right_half[j];
        j++;
        k++;
    }

    return arr;
}

int main() {
    int arr[] = {39, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    merge_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

题目

归并时，左右两侧的队首元素都是6，稳定实现应该先取谁？

题目

已排序的左右区间分别为[1,3]和[4,8]，怎样避免不必要的合并？

对[8,3,7,2,5]按示例代码floor(n/2)拆分。画出整棵递归树；每次合并写出左右队首的比较、选择次序与写回结果。每个单元素区间无需继续拆分。

归并排序

归并排序

归并排序（Merge Sort）

归并排序：递归树的拆分与逐层合并

合并两个有序数组：比较队首，写入第三个数组

归并排序优化

知识测验

知识测验

手工构造归并树

归并排序

归并排序

归并排序（Merge Sort）

归并排序：递归树的拆分与逐层合并

合并两个有序数组：比较队首，写入第三个数组

归并排序优化

知识测验

知识测验

手工构造归并树