概念：

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分治算法 

分阶段        可以理解为就是递归拆分子序列的过程，递归深度为log2n。

治阶段        合并相邻有序子序列，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。 

 所以本质是先分：递归拆成2个2个的比较排序，再治：再相邻两个为单位排好序放入一个新的数组。要求两组排序每组内本身要排好序

C语言代码

#include<stdio.h>
#define len 10000
int temp[len];                       //临时数组用来存放有序数列部分
void merge(int [],int,int,int);     //分治思想的“治”部分，将有序的两个部分合并成一个有序部分
void mergesort(int [],int,int);
int main()
{
    int n,a[1000],i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);            //主函数输入
    mergesort(a,0,n-1);                //归并函数（merge sort）处理
    for(i=0;i<n;i++)                    //输出
        printf("%d ",a[i]);
    return 0;
}

///分治思想的“治”部分，将有序的两个部分合并成一个有序部分
void merge(int a[],int start,int mid,int end)    
{
    int i,j,k=0;
    i=start;j=mid+1;
    while(i<=mid && j<=end)            
    {
        if(a[i]<a[j])
            temp[k++]=a[i++];
        else
            temp[k++]=a[j++];
    }
    
    if(j==end+1)    
    {
        while(i<=mid)
            temp[k++]=a[i++];
    }
    if(i==mid+1)
    {
        while(j<=end)
            temp[k++]=a[j++];
    }
    
    for(i=0,j=start;i<k;i++,j++)
        a[j]=temp[i];
    
}

//递归调用
void mergesort(int a[],int start,int end)
{
    if(start>=end)  return;
    int mid=(start+end)/2;
    mergesort(a,start,mid);
    mergesort(a,mid+1,end);    //先分
    merge(a,start,mid,end);    //再治
    
}

输出结果

归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法
算法复杂度：O（nlogn）
就是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

递归实现

/* 归并排序 - 递归实现 */

#include <stdio.h>
#include<stdlib.h> 
#define ElementType int



/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
     int LeftEnd, NumElements, Tmp;
     int i;
     
     LeftEnd = R - 1; /* 左边终点位置 */
     Tmp = L;         /* 有序序列的起始位置 */
     NumElements = RightEnd - L + 1;
     
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
     }

     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
         
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */ 
     int Center;
     
     if ( L < RightEnd ) {
          Center = (L+RightEnd) / 2;
          Msort( A, TmpA, L, Center );              /* 递归解决左边 */ 
          Msort( A, TmpA, Center+1, RightEnd );     /* 递归解决右边 */  
          Merge( A, TmpA, L, Center+1, RightEnd );  /* 合并两段有序序列 */ 
     }
}

void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
     ElementType *TmpA;
     TmpA = (ElementType *)malloc(N*sizeof(ElementType));
     
     if ( TmpA != NULL ) {
          Msort( A, TmpA, 0, N-1 );
          free( TmpA );
     }
     else printf( "空间不足" );
}


int main()
{
	int A[5]={4,5,3,3,2};
	MergeSort(A,5);
	for(int i=0;i<5;++i)
	{
		printf("%d ",A[i]);
	}
	return 0;
}

迭代实现

#include <stdio.h>
#include<stdlib.h> 
#define ElementType int

/* 归并排序 - 迭代实现 */

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
     int LeftEnd, NumElements, Tmp;
     int i;
     
     LeftEnd = R - 1; /* 左边终点位置 */
     Tmp = L;         /* 有序序列的起始位置 */
     NumElements = RightEnd - L + 1;
     
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
     }

     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
         
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}


/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
     int i, j;
      
     for ( i=0; i <= N-2*length; i += 2*length )
         Merge( A, TmpA, i, i+length, i+2*length-1 );
     if ( i+length < N ) /* 归并最后2个子列*/
         Merge( A, TmpA, i, i+length, N-1);
     else /* 最后只剩1个子列*/
         for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}

void Merge_Sort( ElementType A[], int N )
{ 
     int length; 
     ElementType *TmpA;
     
     length = 1; /* 初始化子序列长度*/
     TmpA = malloc( N * sizeof( ElementType ) );
     if ( TmpA != NULL ) {
          while( length < N ) {
              Merge_pass( A, TmpA, N, length );
              length *= 2;
              Merge_pass( TmpA, A, N, length );
              length *= 2;
          }
          free( TmpA );
     }
     else printf( "空间不足" );
}

int main()
{
	int A[5]={4,5,3,3,2};
	Merge_Sort(A,5);
	for(int i=0;i<5;++i)
	{
		printf("%d ",A[i]);
	}
	return 0;
}

一 、归并排序的思路：

归并排序采用的是分治的思想，就是将数组进行分隔，直到最小的单位(两个元素)，然后对最小的单位进行排序。最后将排好序的单位依次遍历到数组中。

1 将数组进行分隔，直到不能再分的最小单位(两个元素)。
2 将最小单位排序
3 将最小单位遍历到数组中

二、代码

#include <stdio.h>
void merge_part(int arr[], int l, int m, int r)
{
	// 此处应该用 malloc
	int 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++];
		else
			tmp[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)
 
稳定性： 稳定

这个是递归形式的写法，还有非递归形式的。

*注： 个人笔记只用，如果不妥，还望不吝赐教。