归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
基本思路：
先递归的把数组划分为两个子数组，一直递归到数组中只有一个元素，然后再调用函数把两个子数组排好序，因为该函数在递归划分数组时会被压入栈，所以这个函数真正的作用是对两个有序的子数组进行排序；
基本步骤：
1、判断参数的有效性，也就是递归的出口；
2、首先什么都不管，直接把数组平分成两个子数组；
3、递归调用划分数组函数，最后划分到数组中只有一个元素，这也意味着数组是有序的了；
4、然后调用排序函数，把两个有序的数组合并成一个有序的数组；
5、排序函数的步骤，让两个数组的元素进行比较，把大的/小的元素存放到临时数组中，如果有一个数组的元素被取光了，那就直接把另一数组的元素放到临时数组中，然后把临时数组中的元素都复制到实际的数组中；
示例代码：
public class GuibingSort {
//first数组初始索引值，mid数组分界点索引，last数组结束索引，temp[]临时数组
//以mid为界限，将a分为两个数组，对其进行归并排序
//将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，
//谁小就先取谁，取了后就在对应数列中取下一个数。然后再进行比较，
//如果有数列遍历完毕，那直接将另一个数列的数据依次取出即可。
void mergearray(int a[], int first, int mid, int last, int temp[])
{//两个有序数组的归并
int i = first,m = mid;//第一个数组的范围
int j = mid + 1,n = last;//第二个数组的范围
int k = 0;//temp的初始下标
while (i <= m && j <= n)//分别从两个数组中取值
{
if (a[i] <= a[j])//取较小的数放到temp数组中
temp[k++] = a[i++];//先进行赋值运算，然后k，i自加1
//注意，这里j并没有变化，下一次比较仍然是上一次的j值，直到else发生
else
temp[k++] = a[j++];//j变化，i不变化
}
while (i <= m)//如果数组中仍有元素，直接复制到temp后面即可
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)//将排好序的数组重新赋给a
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
//a[]是需要排序的数组，first, last是索引范围
{
if (first < last)//当数组中只有一个元素时，first==last，递归结束
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边递归，直到只剩一个元素
mergesort(a, mid + 1, last, temp); //右边递归，直到只剩一个元素
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
public void sort(int[] a) {
int n=a.length;
int[] b=new int[n];
mergesort(a, 0, n-1, b);
}
public static void main(String[] args) {
int[] a= {10,9,8,7,6,5,4,3};
GuibingSort guibingSort=new GuibingSort();
guibingSort.sort(a);
for (int i : a) {
System.out.println(i);
}
}
}运行过程解释：
第一次归并10和9，排序结果9,10
第二次归并8和7，排序结果7,8
第三次归并9,10和7,8，,排序结果7,8,9,10
对于6,5,4,3排序过程与上述类似，排序结果为3,4,5,6
最后归并两大部分，得到最终结果。