归并是建立在归并操作上的一种有效的排序,该算法是采用分治法（Divide and

Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序，称为二路。

 

算法描述

归并操作的过程如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

 

 

分类
数据结构
最差时间复杂度
最优时间复杂度
平均时间复杂度
最差空间复杂度

 

 

C 代码：

void merge_sort(int src[] , int len){　　 //第一层循环是确定归并的分组    for( int n = 1 ; n <= len ; n <<= 1 ) {　　     //第二岑循环是结合第一层循环确定两个要合并的分组        for( int m = 0 ; m < len ; m += 2*n ) {            //合并两个子分组            for( int nextTuple = m+n ; nextTuple < (m+n*2)>len?len:(m+n*2) ; nextTuple++ ){                for( int prevTuple = m ; prevTuple < nextTuple ; prevTuple++ ){                    if( src[nextTuple] >= src[prevTuple] ){                        int temp = src[nextTuple];                        for(int k = nextTuple ; k > prevTuple ; k--)                        {                            src[k] = src[k-1];                        }                        src[prevTuple] = temp;                    }                }            }        }    }}

运行结果：