本文共 2205 字，大约阅读时间需要 7 分钟。
原理
核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并
算法描述
1.当我们要排序这样一个数组的时候，归并排序法首先将这个数组分成一半
2.然后继续把左边的数组或者序列，进行划分，同理右边的数组或者序列进行划分，递归划分 3.分到一定细度的时候，每一个部分就只有一个元素了，对他们进行一次简单的归并就好了 3.然后把最小的序列，一个个的进行排序，然后再归并Java代码实现
public static void main(String[] args) { int[] arr ={5,4,7,9,3,8,2,1}; mergeSort(arr); } public static void mergeSort(int[] arr) { sort(arr, 0, arr.length - 1); } public static void sort(int[] arr, int L, int R) { if(L == R) { return; } int mid = L + ((R - L) >> 1); sort(arr, L, mid); sort(arr, mid + 1, R); merge(arr, L, mid, R); } public static void merge(int[] arr, int L, int mid, int R) { int[] temp = new int[R - L + 1]; int i = 0; int p1 = L; int p2 = mid + 1; // 比较左右两部分的元素，哪个小，把那个元素填入temp中 while(p1 <= mid && p2 <= R) { temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } // 上面的循环退出后，把剩余的元素依次填入到temp中 // 以下两个while只有一个会执行 while(p1 <= mid) { temp[i++] = arr[p1++]; } while(p2 <= R) { temp[i++] = arr[p2++]; } // 把最终的排序的结果复制给原数组 for(i = 0; i < temp.length; i++) { arr[L + i] = temp[i]; } } 补充 << 、>>、>>>运算
左移运算符（<<）
将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。
例：a = a<< 2将a的二进制位左移2位，右补0，
左移1位后a = a *2;
若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。
右移运算符（>>）
将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。
操作数每右移一位，相当于该数除以2。
例如：a = a>> 2 将a的二进制位右移2位，
左补0 or 补1得看被移数是正还是负。
运算符把expression1 的所有位向右移 expression2指定的位数。expression1的符号位被用来填充右移后左边空出来的位。向右移出的位被丢弃。
例如，下面的代码被求值后，temp 的值是 -4：
-14 （即二进制的 11110010）右移两位等于 -4（即二进制的 11111100）。
var temp = -14 >> 2
注意：负数在转换成二进制的时候，反码+1变成补码的时候，也是可以进一位的
负数的： 十进制变二进制：原码–反码–加一（补码）； 二进制变十进制：减一–反码–原码。
无符号右移运算符（>>>）
运算符把 expression1 的各个位向右移expression2 指定的位数。右移后左边空出的位用零来填充。移出右边的位被丢弃。
例如：var temp = -14 >>>2
变量 temp的值为 -14 （即二进制的 11111111 11111111 1111111111110010），向右移两位后等于 1073741820 （即二进制的 00111111 11111111 1111111111111100）。
算法复杂度
时间复杂度：O(nlogn)
O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序 稳定性：归并排序是稳定的排序算法，temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];这行代码可以保证当左右两部分的值相等的时候，先复制左边的值，这样可以保证值相等的时候两个元素的相对位置不变 应用场景
100G的文件，如何用100M内存进行排序？
转载地址：http://qzcii.baihongyu.com/