假设：大家期末考试完，你们老师让你们去机房写一个程序，自动实现班级学生排名。那么这道题应该怎么做呢？貌似以前的C++基础语法知识根本解决不了。那么，今天，我们要来介绍一个C++进阶知识，就是算法系列中的归并排序算法。具体是什么呢？
 请看：
 题目：输入n个数（n<=10000），对这些数从小到大排序。
 解题程序：归并排序算法的思路
 
 
 
 
 这个我们只会列出程序，想知道更多的需要购买我们相应的课程。已经购课的同学就把这个再当做一次复习课吧。
 
排序算法也是信息学竞赛中常见的考点。看到这个大家肯定会觉得比以前猿博士提到的那些C++基础语法知识难度又上来了。想理解得更深刻的可以查看：NOIP信息学奥赛通关-36归并排序 - 网易云课堂 https://study.163.com/course/courseMain.htm?courseId=1209418807&share=2&shareId=480000001918401
 
现在随着全面人工智能时代的到来，少儿编程已是大势所趋，C++信息学编程是重点学习内容之一。
 
猿博士课堂是智慧猿少儿编程课堂打造的一个知识性栏目。宗旨在于针对少儿编程学习中遇到的问题答疑解惑，同时提供解题思路，训练计算思维，为成长助力。智慧猿少儿编程课堂一直致力于中国青少年的少儿编程普惠教育，立志做让对信息学编程感兴趣的青少儿学得起、学得懂、学得会的编程课。自上线以来也得到了很多家长学员的支持，为了回馈学员和家长，我们的课程最近开始新一轮促销。最低一折起，敬请关注！大家想学习的归并排序算法也在促销。这样的好消息一般人我是不告诉的。快来抢购吧。

1、归并算法的概念：
 
归并排序是一种概念上最简单的排序算法，与快速排序一样，归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。
 
2、归并算法的流程：
 
 
3、归并算法分析：
 
归并算法主要是先将原数组通过递归调用进行分割，使之形成一个个独立的数组，之后借助temp数组，将数组进行合并，注意合并时，从栈顶向栈底方向。
 
4、代码实现：
 
import java.util.Arrays;
//归并排序，使用temp这一个额外的数组来合并merge的数组，并将其多次赋值给array，知道合并完成时，temp内的数组序列才与array内的一致。
public class mergeSort {
	public static void main(String[] args) {
	int[] array= {8,4,5,7,1,3,6,2};
	int[] temp = new int[array.length];
	sort(array,0,array.length-1,temp);
	System.out.println(Arrays.toString(array));
	}
	//分割数组
	public static void sort(int[] array,int left,int right,int[] temp) {
		if(left<right) {
			int mid = (left+right)/2;
			sort(array,left,mid,temp);//向左将array进行分割
			sort(array,mid+1,right,temp);//向右将array进行分割
			merge(array,left,mid,right,temp);//调用是将分割好的数组从栈顶到栈底开始往下合并
		}
	}
	//合并数组
	public static void merge(int[] array,int left,int mid,int right,int[] temp) {
		int i = left;//初始化i,左边有序序列的初始索引
		int j = mid+1;//初始化j，右边序列的初始索引
		int t = 0;//指向temp数组的当前索引
		while(i<=mid&&j<=right) {
			if(array[i]<=array[j]) {
				temp[t] = array[i];
				t+=1;
				i+=1;
			}
			else {
				temp[t] = array[j];
				t+=1;
				j+=1;
			}
		}
		while(i<=mid) {
			temp[t] = array[i++];
			t++;
		}
		while(j<=right) {
			temp[t] = array[j++];
			t++;
		}
		int templeft = left;
		t = 0;
		//将temp内的数组赋值给array数组
		while(templeft<=right) {
			array[templeft] = temp[t];
			templeft++;
			t++;
		}
	}
}

 
5、输出：
 
[1, 2, 3, 4, 5, 6, 7, 8]

归并排序首先进行的是对序列拆分。
 
先把代码看成已经执行到最后一步，左部分和右部分都是排序好的，然后把他们的左部分和右部分再排序，剩下的几次排序可以采用嵌套递归来实现。
 
代码如下：
 
#归并排序
def merge_sort(alist):
    n=len(alist)
    if n<=1:       #如果只有一个元素的话就不能再往下拆分了，直接返回
        return alist  #不断归并到最后一个列表只有一个元素，把自身返回即可。
    mid=n//2        #中间位置下标
    #left 采用归并排序后形成的新的有序的新的列表
    left_li=merge_sort(alist[:mid])     #左部分列表,调用自身
    #right 采用归并排序后形成的新的有序的新的列表
    right_li=merge_sort(alist[mid:])     #右部分列表，调用自身
 
    #这个时候返回的左部分是经过多次递归后形成的一个有序的左部分，右部分也是一样
    #这个时候就要把左右两部分进行合并,将两个有序的子序列合并成一个新的整体。
    #merge(left,right)
 
    #接下来是合并
    left_pointer,right_pointer=0,0         #left_pointer和right_pointer刚开始都应该指向第一个元素
    result=[]                             #建立新的列表来存放合并的结果值
 
    while left_pointer<len(left_li) and right_pointer<len(right_li):  #当两个指针都没有走到头的时候执行判断大小，并选择小的加入result列表代码
        if left_li[left_pointer] <=right_li[right_pointer]:   #这里加等号是为了确保代码的稳定性
            result.append(left_li[left_pointer])
            left_pointer+=1
        else:
            result.append(right_li[right_pointer])
            right_pointer+=1
    #当一边游标到头另一边的游标还没有到头的时候，把剩下的追加上，到头的追加空列表，没到头的把剩下的全部追加上
    result+=left_li[left_pointer:]
    result+=right_li[right_pointer:]
    #到这里排序的新列表制作完成
    return result  #把新生成的列表返回
 
if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55,20]
    print(alist)
    sorted=merge_sort(alist)
    print(sorted)

归并排序是采用分治法的一个非常典型的应用，另一个可以采用分治法的是快速排序，归并算法比快速排序速度稍低。归并排序的思想就是先递归分解数组，再合并数组。
 
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
 
如　设有数列{6，202，100，301，38，8，1}
 
初始状态：6,202,100,301,38,8,1
 
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
 
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
 
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
 
总的比较次数为：3+4+4=11；
 
逆序数为14；
 
python实现：
 
def merge_sort(alist):
    """
    递归分治序列
    :param alist:
    :return:
    """
    if len(alist) <= 1:
        return alist
    num = len(alist)//2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    return merge(left, right)  # 合并

def merge(left, right):
    """
    合并操作
    :param left:
    :param right:
    :return:
    """

    l, r = 0, 0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:  # 筛选排序将left与right最小元素按序加入新序列
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result