归并排序的实质就是将数据先划分为小组，在两个相邻小组内部排序之后，再扩大小组进行排序
注意：
1、在两个小组内部排序的时候，需要用到一个辅助数组，来将两个小组中的数据进行排序，排完序之后，将辅助数组中的数据拷贝回原数组中的适当位置即可
2、再求mid时，有一个简单的防止溢出，快捷的方法，mid = left + ((right - left) >> 1); 但是要注意到+的优先级高于 >>，所以在进行位计算时，要加上括号
时间复杂度 O(NlogN) 空间复杂度O(N)
public void mergeSort(Integer[] arrays){ if(arrays.length == 0) return; mergeSort(arrays, 0, arrays.length - 1); } public void mergeSort(Integer[] arrays, int left, int right){ if(left >= right) return; int mid = ((right - left) >> 1) + left; mergeSort(arrays, left, mid); mergeSort(arrays, mid + 1, right); Integer [] help = new Integer[right - left + 1]; int i = 0; int x = left, y = mid + 1; while(x <= mid &&y <= right){ help[i++] = arrays[x] < arrays[y] ? arrays[x++] : arrays[y++]; } while(x <= mid){ help[i++] = arrays[x++]; } while(y <= right){ help[i++] = arrays[y++]; } i = 0; while(i < help.length){ arrays[left + i] = help[i++]; } }
更加直观的写法（推荐）因 为这样有一个方法用来进行分组，另外一个方法 进行融合， 更加直观
package sort;import static sort.PrintRes.print;/** * Created by Skye on 2018/4/2. */public class MergeSort { public void mergeSort(Integer[] arrays){ if(arrays.length == 0) return; mergeSortEasy(arrays, 0, arrays.length - 1); } public void mergeSortEasy(Integer[] arrays, int left, int right){ if(left >= right) return; int mid = left + ((right - left) >> 1); mergeSortEasy(arrays, left, mid); mergeSortEasy(arrays, mid + 1, right); merge(arrays, left, mid, right); } public void merge(Integer[] arrays, int left, int mid, int right){ int i = 0; int [] help = new int[right - left + 1]; int x = left; int y = mid + 1; while(x <= mid && y <= right){ help[i++] = arrays[x] < arrays[y] ? arrays[x++] : arrays[y++]; } while(x <= mid){ help[i++] = arrays[x++]; } while(y <= right){ help[i++] = arrays[y++]; } i = 0; while(i < help.length){ arrays[left + i] = help[i++]; } }}
相关问题：
小和问题在一个数组中， 每一个数左边比当前数小的数累加起来， 叫做这个数组的小和。 求一个数组的小和。例子：[1,3,4,2,5]1左边比1小的数， 没有；3左边比3小的数， 1；4左边比4小的数， 1、 3；2左边比2小的数， 1；5左边比5小的数， 1、 3、 4、 2；所以小和为1+1+3+1+1+3+4+2=16
逆序对问题在一个数组中， 左边的数如果比右边的数大， 则折两个数构成一个逆序对， 请打印所有逆序对