合并排序（Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
最坏时间复杂度 O(nlogn)
合并排序是稳定的排序算法
- #include <stdio.h>
- #include <stdlib.h>
- void merge(int a[], int p, int q, int r)
- {
- int i, j, k;
- int *temp = (int *)malloc((r - p + 1) * sizeof(int));
- i = p;
- j = q + 1;
- k = 0;
- while ((i <= q) && (j <= r)) {
- if (a[i] < a[j])
- temp[k] = a[i++];
- else
- temp[k] = a[j++];
- k++;
- }
- while (i <= q)
- temp[k++] = a[i++];
- while (j <= r)
- temp[k++] = a[j++];
- for (i = 0; i < r - p + 1; i++) {
- a[p+i] = temp[i];
- }
- free(temp);
- }
- void merge_sort(int a[], int p, int r)
- {
- int q;
- if (p < r) {
- q = (p + r) / 2;
- merge_sort(a, p, q);
- merge_sort(a, q + 1, r);
- merge(a, p, q, r);
- }
- }
- int main()
- {
- int a[] = {5,2,4,7,1,3,2,6}, i;
- int p = 0, r = sizeof(a) / sizeof(int);
- merge_sort(a, p, r);
- for (i = 0; i < r; i++)
- printf("%d ", a[i]);
- return 0;
- }
12-18行选择最小的元素复制到temp，19-22行将剩余序列的元素复制到temp，24-26行将排好序的序列复制到数组。