【八大排序之归并排序】

归并排序

1.申请空间，该空间用来存放合并后的序列；

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3.比较两个指针所指向的元素，选择相对小的元素放入到申请的列表中，并移动指针到下一位置；

4.重复步骤 3 直到某一指针达到序列尾；

5.将另一序列剩下的所有元素直接复制到申请列表列尾。

public static void sort(int[] arr,int left,int right) {
		
		if(left >=right) {
			return;
		}
		int mid =(left +right)/2;
		sort(arr,left,mid);
		sort(arr,mid+1,right);
		
		arrsort(arr,left,mid,right);
	}
 
	public static void arrsort(int[] arr, int left, int mid, int right) {
		// TODO Auto-generated method stub
		int[] temp =new int[right -left+1];
		int s1 =left;
		int s2 =mid+1;
		int index =0;
		while(s1<=mid&&s2<=right) {
			
			if(arr[s1]<arr[s2]) {
				temp[index] =arr[s1];
				index++;
				s1++;
			}else {
				temp[index] =arr[s2];
				index++;
				s2++;
			}			
		}
		//将s1剩余元素放入数组
		while(s1<=mid) {
			temp[index] =arr[s1];
			index++;
			s1++;
		}
		//将s2剩余元素放入数组
		while(s2<=right) {
			temp[index] =arr[s2];
			index++;
			s2++;
		}
		
		for(int j=0;j <temp.length;j++) {
			arr[j+left] =temp[j];
		}
	}