归并排序（Merge sort）

思想：分治

方法： 分为自顶向下和自低向上两种。

1. 自顶向下递归：

#include<stdio.h>
#include<stdlib.h>
/*#include<time.h>*/
#define MAX 10
int numbers[MAX]={0};
int temp[MAX] = {0};

void mergeSort(int[], int); /* 提á供?接ó口ú */
void m_sort(int[], int[], int, int); /* 分?割?排?序ò */
void merge(int[], int[], int, int, int); /* 归é并￠ */

void mergeSort(int numbers[], int temp[], int array_size)
{
    m_sort(numbers, temp, 0, array_size - 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
    int mid;
    if (right > left)
    {
        mid = (right + left) / 2;
        m_sort(numbers, temp, left, mid);
        m_sort(numbers, temp, mid+1, right);
        merge(numbers, temp, left, mid+1, right);

    }
}
void merge(int numbers[], int temp[], int left, int mid, int right) // left -> mid-1, mid -> right two sequences
{
    int start1 = left, start2 = mid;
    for(int j = left; j <= right; ++j)
    {
        if (start1 < mid && (numbers[start1] < numbers[start2] || start2 > right)) temp[j] = numbers[start1++];
        else temp[j] = numbers[start2++];
    }
    for (int i = left; i <= right; i++)
        numbers[i] = temp[i];
}
void init_array()
{
    int i;
    /*srand((unsigned) time(NULL));*/
    for(int i = 0; i < MAX; i++)
        numbers[i] = rand() % MAX;
}
void print_array()
{
    int i;
    for(i = 0; i < MAX; i++)
        printf("%d	", numbers[i]);
}
int main()
{
    init_array();
    mergeSort(numbers, temp, MAX);
    print_array();
    printf("
");
    return 0;
}

2.自底向上排序（非递归）

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define N 1000000
int A[N]={0}; // data
int T[N] = {0};  // work array
void BottomUpMerge(int A[], int iLeft, int iRight, int iEnd, int B[]);

void BottomUpSort(int A[], int T[], int n)
{
    int width;
    for (width = 1; width < n; width = 2 * width)
    {
        int i, j;
        for (i = 0; i < n; i = i + 2 * width)
        {
            BottomUpMerge(A, i, MIN(i+width, n), MIN(i+2*width, n), T);
        }
        for(j = 0; j < n; ++j) 
            A[j] = T[j];
    }
}
void BottomUpMerge(int A[], int iLeft, int iRight, int iEnd, int T[])
{
    int i0 = iLeft, i1 = iRight, j;
    for (j = iLeft; j < iEnd; j++)
    {
        if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
            T[j] = A[i0++];
        else
            T[j] = A[i1++];
    }
}
int main()
{
    init_array();
    BottomUpSort(A, T, N);
    print_array();
    printf("
");
    return 0;
}

稳定排序。空间复杂度 O(n)。时间复杂度 O(nlgn)，如图：

精简代码

（自顶向下）

void merge_sort(int A[], int T[], int left, int right){ // right = n-1;
	if (right > left){
		int mid = (right + left) / 2;
		merge_sort(A, T, left, mid);
		merge_sort(A, T, mid+1, right);
		merge(A, T, left, mid+1, right);
	}
}
void merge(int A[], int T[], int s1, int s2, int last){
	int tag1 = s1, tag2 = s2;
	for(int j = s1; j <= last; ++j) {
		if(s1 < tag2 && (A[s1] <= A[s2] || s2 > right)) T[j] = A[s1++];
		else T[j] = A[s2++];
	}
	for (int i = tag1; i <= last; i++) A[i] = T[i];
}

 （自底向上）：Ο(n(logn)²) time complexity.

void Merge(int A[], vector<int>& T, int s1, int s2, int end) {
	int tag = s2;
	for(int j = s1; j < end; ++j) 
		if(s1 < tag && (A[s1] <= A[s2] || s2 >= end)) T[j] = A[s1++];
		else T[j] = A[s2++];
}
void MergeSort(int A[], int n) {
	vector<int> T(n);
	for(int width = 1; width < n; width *= 2){
		for(int start = 0; start < n; start += 2*width)
			Merge(A, T, start, min(start+width, n), min(start+2*width, n));
		for(int i = 0; i < n; ++i) A[i] = T[i];
	}
}