[归并排序]-Java实现归并排序

排序思想：分治思想，先将原数组一直二分为单个元素，然后按顺序进行合并，利用递归进行循环 *** 作。

编程思想：将数组看成是两个，left-mid（中间值） 和 （mid+1 - right）且将合并过程看成是合并两个有序表
时间复杂度：O(nlogn)

// 合并(合并两个有序表)
public void merge(int [] arr,int left, int mid,int right,int [] temp){
	int i =left;
	int j = mid + 1;
	int t =0;
	 
	 while(i <= mid && j <= right){
	 	if(arr[i] <= arr[j]){
	 		temp[t] = arr[i];
	 		t++;
	 		i++;
	 	}else(arr[i] > arr[j]){
	 		t++;
	 		j++;
	 	}
	 }
	while(i <= mid){
		temp[t] = arr[i];
		t++;
		i++;
	}
	while( j <= right){
		temp[t] = arr[j];
		t++;
		j++;
	}

	//将temp赋值到arr
	t = 0;
	int tempLeft = left;
	while(tempLeft <= right){
		arr[tempLeft] = temp[t];
		t++;
		tempLeft++;
	}
}


//分解
public int [] mergeSort(int [] arr, int left ,int right,int [] temp){
	int mid = (left + right)/2;
	//左递归
	mergeSort(arr,left,mid,temp);
	//右递归
	mergeSort(arr,mid+1,right,temp);
	//合并
	merge(arr,left,mid,right,temp);
	return arr;
}