一 、归并排序的思路：
归并排序采用的是分治的思想，就是将数组进行分隔，直到最小的单位(两个元素)，然后对最小的单位进行排序。最后将排好序的单位依次遍历到数组中。
1 将数组进行分隔，直到不能再分的最小单位(两个元素)。2 将最小单位排序3 将最小单位遍历到数组中
二、代码
#include <stdio.h>void merge_part(int arr[], int l, int m, int r){// 此处应该用 mallocint tmp[256] = {0 };int idx = l, i = l, j = m + 1, ii = l;for (; i <= m && j <= r;){if (arr[i] < arr[j])tmp[idx++] = arr[i++];elsetmp[idx++] = arr[j++];}if (i <= m) {for (; i <= m; ++i)tmp[idx++] = arr[i];}if (j <= r) {for (; j <= r; ++j)tmp[idx++] = arr[j];}for (; ii <= r; ++ii)arr[ii] = tmp[ii];}void merge_sort(int arr[], int l, int r){int mid = ((r - l) / 2) + l;if (l >= r) return;merge_sort(arr, l, mid);merge_sort(arr, mid + 1, r);merge_part(arr, l, mid, r);}int main(){int arr[] = {8, 36, 23, 2, 17, 6, 59, 20, 13, 28, 14, 83, 9};//int arr[] = { 8, 36, 23, 2, 17, 6 };int N = sizeof(arr) / sizeof(int), i = 0;for (i = 0; i < N; ++i) {printf("%d ", arr[i]);}printf("\n");merge_sort(arr, 0, N - 1);for (i = 0; i < N; ++i) {printf("%d ", arr[i]);}printf("\n");return 0;}
三、排序流程
从上到下，从左到右是程序的执行流。
归并排序的复杂度：
时间复杂度：- 平均情况：O(nlogn)- 最好情况：O(nlogn)- 最坏情况：O(nlogn)空间复杂度：- 辅助空间：O(n)稳定性： 稳定
这个是递归形式的写法，还有非递归形式的。
*注： 个人笔记只用，如果不妥，还望不吝赐教。
