C语言归并排序

归并排序是一种分治法的排序算法，它将数组分成两个子数组，分别排序后再合并。其时间复杂度为O(n log n)，适合处理大规模数据的排序。

图解递归过程以及复杂度

代码实现

#include <stdio.h>

#define SIZE(a) (sizeof(a)/sizeof(a[0]))
#define N 7

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

void merge_sort(int arrp[], int n);
int main(void) {

 int arr[N] = { 38,27,43,3,9,82,10 };
 print_array(arr, N);
 merge_sort(arr,N);

 return 0;
}
int tmp[N];
void merge(int arr[], int left, int mid, int right) {
 int i = left, j = mid + 1, k = left;
 while (i <= mid && j <= right)
 {
  if (arr[i] <= arr[j])
  {
   tmp[k++] = arr[i++];
  }
  else
  {
   tmp[k++] = arr[j++];
  }
 }
 while (i <= mid)
 {
  tmp[k++] = arr[i++];
 }
 while (j <= right)
 {
  tmp[k++] = arr[j++];
 }
 for (int k = left; k <= right; k++) {
  arr[k] = tmp[k];
 }
}
void m_sort(int arr[], int left, int right) {
 if (left >= right)
 {
  return;
 }
 int mid = left + (right - left >> 1);
 m_sort(arr, left, mid);
 m_sort(arr, mid + 1, right);
 merge(arr, left,mid, right);

 print_array(arr, N);
}

void merge_sort(int arr[], int n) {
 m_sort(arr, 0, n - 1);
}

代码运行结果

初始数组为：

38 27 43 3 9 82 10

排序过程中的数组变化：

38 27 43 3 9 82 10
27 38 43 3 9 82 10
27 38 3 43 9 82 10
3 27 38 43 9 82 10
3 27 38 43 9 82 10
3 27 38 43 9 10 82
3 9 10 27 38 43 82