别在这里问什么是归并排序，请善用搜索引擎，数据结构系列的学习笔记只是我用来整理，归纳和复习的系列，不会说原理。

相关代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//
// Created by Tianyi on 2021/11/10.
//
#include <iostream>

using namespace std;


void merge_sort_c(int *arr, int start, int end);
void merge(int *arr, int start, int mid, int end);
void show(int *arr, int len);


void marge_sort(int *arr, int len) {
    if (len <= 1) {
        return;
    }

    merge_sort_c(arr, 0, len - 1);
}


void merge_sort_c(int *arr, int start, int end) {
    if (start >= end) {
        return;
    }

    int mid = (start + end) / 2;

    // 切左边
    merge_sort_c(arr, start, mid);
    // 切右边
    merge_sort_c(arr, mid + 1, end);

    // 合并左右切片
    merge(arr, start, mid, end);
}


void merge(int *arr, int start, int mid, int end) {
    // 计算当前 大切片 的长度
    int len = end - start + 1;
    // 申请一个临时的数组用于存储 大切片 的正确顺序
    int *tempArr = new int[len];
    // 初始化 大切片 下标
    int tempIndex = 0;

    // 左切片起始位置
    int leftIndex = start;
    // 右切片起始位置
    int rightIndex = mid + 1;

    // 对两个切片进行比较，依次放入临时数组
    while (leftIndex <= mid && rightIndex <= end) {
        if (arr[leftIndex] >= arr[rightIndex]) {
            tempArr[tempIndex] = arr[rightIndex];
            rightIndex++;
        } else {
            tempArr[tempIndex] = arr[leftIndex];
            leftIndex++;
        }

        tempIndex++;
    }

    // 用于临时存储剩余切片的起始位置和终止位置
    int residueIndex;
    int residueEnd;
    // 判断是左切片没有存储还是右切片没有存储
    if (leftIndex <= mid) {
        residueIndex = leftIndex;
        residueEnd = mid;
    } else {
        residueIndex = rightIndex;
        residueEnd = end;
    }
    // 将剩余的切片存入临时数组中
    while (residueIndex <= residueEnd) {
        tempArr[tempIndex] = arr[residueIndex];
        tempIndex++;
        residueIndex++;
    }

    // 打印步骤
    show(tempArr, len);

    // 将正确的顺序覆盖到原来的数组中
    for (int i = start, tempIndex = 0; i <= end; i++, tempIndex++) {
        arr[i] = tempArr[tempIndex];
    }

    // 释放临时数组使用的内存
    free(tempArr);
}


void show(int *arr, int len) {
    for (int i = 0; i < len; ++i) {
        cout << "(" << arr[i] << ")" << " - ";
    }
    cout << endl;
}


int main() {
    int arr[] = {5, 3, 6, 2, 1, 4, 0, -7, -9, -3, -6, -1};

    int len = sizeof(arr) / sizeof(int);

    marge_sort(arr, len);
    show(arr, len);

    return 0;
}