归并排序的两种方式

概述

归并排序是目前最高效的排序算法之一，它兼具稳定和低复杂度的特点，其最坏时间复杂度O(nlogn)，空间复杂度O(n)。

归并排序采用计算机科学的分治思想，因此有两种实现方式：自顶向下和自底向上。

自顶向下

针对分治问题，自顶向下是一张常见且较为简便的方式，它采用递归操作。

因此归并排序的原理也就清楚了，首先将数组拆分为两个，进行递归调用，然后合并排序结果。

---

这是一种可能的自顶向下C实现：

c
void merge(int arr[], unsigned sta, unsigned mid, unsigned end)
{
  int tmp[end - sta];
  unsigned i = sta, j = mid, k = 0;

  while (i < mid && j < end)
  {
    tmp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
  }

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

  while (j < end)
  {
    tmp[k++] = arr[j++];
  }

  for (size_t i = sta; i < end; i++)
  {
    arr[i] = tmp[i - sta];
  }
}

void split_merge(int arr[], unsigned sta, unsigned end)
{
  if (end - sta < 2) return;

  unsigned mid = (sta + end) / 2;

  split_merge(arr, sta, mid);
  split_merge(arr, mid, end);
  merge(arr, sta, mid, end);
}

void sort(int arr[], unsigned n)
{
  split_merge(arr, 0, n);
}

自底向上

自底向上与自上而下相反，从单个元素开始进行merge和排序，直至所有元素被merge。

---

这是一种可能的自底向上C实现，它与自顶向下使用相同的merge函数：

c
#define MIN(x, y) (((x) < (y)) ? (x) : (y))

void sort(int arr[], unsigned n)
{
  for (size_t i = 1; i < n; i *= 2)
  {
    for (size_t j = 0; j < n; j += 2 * i)
    {
      merge(arr, j, MIN(j+i, n), MIN(j+i*2, n));
    }
  }
}

总结

两种方式都可以实现归并排序。

对于自底向上，由于免去递归，在n很大时，可以避免调用栈溢出。