import java.util.Arrays;

public class Cao46

{

/**

* @归并排序

*

* 三个指针：两个指针最初位置分别为两个已经排序序列的起始位置，第三个指针两个序列的中间位置

* 两个方法：一个是递归方法

* 一个是合并方法，每一趟将最多含2的n次方个元素的单元排序

* 工作原理：

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

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

3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

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

5、将另一序列剩下的所有元素直接复制到合并序列尾

*/

public static void main(String[] args)

{

int[] array={1,6,3,2,5,9,4,7};

sort(array,0,array.length-1);

System.out.println(Arrays.toString(array));//打印数组

}

public static void sort(int[] array, int left, int right) {

if (left<right)

{

//找出中间索引

int center=(left+right)/2;

//对左边数组进行递归

sort(array,left,center);

//对右边数组进行递归

sort(array,center+1,right);

//合并

merge(array,left,center,right);

}

}

public static void merge(int[] array, int left, int mid, int right) {

int[] temp = new int[right - left + 1];

int l = left;// 左指针

int r = mid + 1;// 右指针

int k = 0;//临时数组指针

// 把较小的数先移到新数组中

while (l<= mid && r <= right)

{

if (array[l] < array[r])

{

temp[k++] = array[l++];

}

else

{

temp[k++] = array[r++];

}

}

// 把左边剩余的数移入数组

while (l <= mid)

{

temp[k++] = array[l++];

}

// 把右边边剩余的数移入数组

while (r <= right)

{

temp[k++] = array[r++];

}

// 把新数组中的数覆盖array数组

System.arraycopy(temp, 0, array, left, right - left + 1);

}

}