package Sort;
 
import java.util.Arrays;
/**
 * 歸并排序：
 * 
 * 利用歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，
 * 
 * 而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起，即分而治之)。
 * @author lenovo
 *
 */
public class MergeSort {
	public static void main(String[] args) {
		int[] a= {5,8,6,3,9,8,7,1,4,21,-8,46};
		int[] temp=new int[a.length];
		mergeSort(a, 0, a.length-1, temp);
		System.out.println(Arrays.toString(a));
	}
	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 l=left;//左邊序列的起始位置
		int r=mid+1;//右邊序列的起始位置
		int t=0;//中間數(shù)組的當(dāng)前元素下標(biāo)
		while(l<=mid &&r<=right ) {//左邊或右邊沒結(jié)束
			//那邊小就將那邊的元素放入到臨時(shí)數(shù)組中
			if(arr[l]<=arr[r]) {
				temp[t++]=arr[l++];
			}else {
				temp[t++]=arr[r++];
			}
		}
		//while循環(huán)結(jié)束，說明有一邊已經(jīng)遍歷完畢，將另一邊剩余的元素放入到臨時(shí)數(shù)組中
		while(l<=mid) {
			temp[t++]=arr[l++];
		}
		while(r<=right) {
			temp[t++]=arr[r++];
		}
		//將臨時(shí)數(shù)組中的有序序列copy到原數(shù)組中
		t=0;
		int templeft=left;
		while(templeft<=right) {
			arr[templeft++]=temp[t++];
		}
	}
}