归并排序（简单易懂）

解题思路:

注意事项:

参考代码:
import java.util.Scanner;

public class Main
{

//Main
   public static void main(String[] args)
   {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int arr[] = new int[n];
       for (int i = 0; i < n; i++) {
           arr[i] = sc.nextInt();
       }
       int[] temp = new int[arr.length];
       mergeSort(arr,0,arr.length-1,temp);
       for (int i = 0; i <arr.length; i++) {

                   System.out.print(arr[i]+" ");
       }
   }

//分+合的方法
public static void mergeSort(int[] arr,int left,int right,int[] temp)
{
   if(left<right)
   {
       int mid = (left + right)/2;
       //向左递归分解
       mergeSort(arr,left,mid,temp);
       //向右递归分解
       mergeSort(arr,mid+1,right,temp);
       //每分解一次就合并一次
       merge(arr,left,mid,right,temp);
   }
}
//合并方法
public static void merge(int arr[],int left,int mid,int right,int[] temp)
{
   int i = left;//左边有序数列的初始索引
   int j = mid+1;//右边有序序列的初始索引
   int t= 0;//指向temp的当前索引
   //先把左右两边数据按规则填充到temp数组，直到两边有一边处理完毕为止
   while (i<=mid&&j<=right)
   {
       /*
       如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
       将左边该元素拷贝到temp数组
        */
       if(arr[i]<=arr[j])
       {
           temp[t] = arr[i];
           t+=1;
           i+=1;
       }
       else{
           temp[t] = arr[j];
           t+=1;
           j+=1;
       }
   }
   //把剩余数组数据依次全部填充到temp
   while(i<=mid)
   {
       temp[t] = arr[i];
       t += 1;
       i += 1;
   }
   while(j<=right)
   {
       temp[t] = arr[j];
       t += 1;
       j += 1;
   }
   //将temp数组元素拷贝到arr
   //并不是每一次都拷贝所有
   t = 0;
   int tempLeft = left;
   System.out.println("tf="+tempLeft+" "+"ri="+right);
   while(tempLeft<=right)
   {
       arr[tempLeft] = temp[t];
       t += 1;
       tempLeft += 1;
   }
}

}