递归--二分归并排序算法（JAVA）

输入n为数组大小，并输入n个数据，使用归并排序的算法将该数组按由小到大的顺序排列，并将排列后的数组输出

1. 把长度为n的输入序列分成两个长度为n/2的子序列；

2. 将这两个子序列分别采用归并排序；

3. 将两个排好序的子序列合并成一个最终序列。

以数组：**{29,38,65,87,23,27,72}**为例：

1. 先将数组划分为两个子数组，如将 {29,38,65,87,23,27,72} 分为 {29,38,65,87} 和 {78,23,27,72}
2. 再将两个划分好的数组分别再划分为两个子数组：如将 {29,38,65,87} 分为 {29,38} {65,87} 和将**{78,23,27,72}** 分为 {78,23}{27,72}
3. 一直划分下去，直到不能再划分为止，即每个子数组只有一个元素

此时可以将整个分的过程看成一个满二叉树：

（注意：比较时，从二叉树的最下层开始向上层逐一合并）

1. 将不能再分的相邻子数组进行比较，比较后的子数列合并为一个数组，如将**{29}和{38}合并为{29,38}，将{65}** 和 {87}合并为{65,87}，将 {78} 和 {23} 合并为 {23,78}，将 {27} 和 {72} 合并为 {27,72}
2. 再将合并好的四个数组（（{29,38}，{65,87}），（{23,78}，{27,72}））两两进行比较，然后合并为两个新数组**{29,38,65,87}和{23,27,72,78}**
3. 最后将两个新数组（{29,38,65,87}，{23,27,72,78}）合并为一个最终排列好的数组**{23,27,29,38,65,72,78,87}**
   

import java.util.Scanner;

public class 分治_3二分归并排序
{

    // 只有不能再分时，才被调用，并且
	public static void Merge(int[] A, int[] B, int left, int mid, int right)
	{
		int i = left;
		int j = mid + 1;
		int flag = 0;
        
        // 比较以及合并的过程
		while (i <= mid && j <= right)
		{
            // 当左子数组第i个元素小于等于右子数组第j个元素时
			if (A[i] <= A[j])
			{
                // 将左子数组第i个元素接在B数组后面
				B[flag] = A[i];
                // 数组 B 向后移一位
				flag++;
                // 左子数组先后移一位
				i++;
			}
            // 否则，当左子数组第i个元素大于右子数组第j个元素时
            else
			{
                // 将右子数组第j个元素接在B数组后面
				B[flag] = A[j];
                // 数组 B 向后移一位
				flag++;
                // 右子数组先后移一位
				j++;
			}
		}
        
        // 当左边子数组有剩余时，将左边子数组剩余的所有元素接在数组B后
		while (i <= mid)
		{
			B[flag] = A[i];
			flag++;
			i++;
		}
        // 当右边子数组有剩余时，将右边子数组剩余的所有元素接在数组B后
		while (j <= right)
		{
			B[flag] = A[j];
			flag++;
			j++;
		}

		// 每次将排好序的数组 B 复制到数组 A 里面
		flag = 0;
		while (left <= right)
		{
			A[left] = B[flag];
			left++;
			flag++;
		}
	}

	public static void Merge_Sort(int[] A, int[] B, int left, int right)
	{
		if (left < right)
		{
            // mid 为分隔点，即left~mid为左子数组，(mid+1)~right为右子数组
			int mid = (left + right) / 2;

			// 将数组 A 分成左子数组和右子数组后，分别递归调用Merge_Sort()
			Merge_Sort(A, B, left, mid);
			Merge_Sort(A, B, mid + 1, right);

			// 划分到不能再划分时，进行合并
			Merge(A, B, left, mid, right);
		}
	}

	public static void main(String[] args)
	{
		// TODO 自动生成的方法存根
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int[] A = new int[n];
        // B 数组为一个临时数组
		int[] B = new int[A.length]; 
		for (int i = 0; i < n; i++)
		{
			A[i] = input.nextInt();
		}
		input.close();

		Merge_Sort(A, B, 0, A.length - 1);

		for (int i = 0; i < A.length; i++)
			System.out.printf(A[i] + " ");
	}

}