普通的归并排序，需要一个额外的数组来保存每次merge的结果；如果要求不使用额外空间，那么每次merge的时候需要做一些处理。
思路：
- 合并left[] 和 right[]时，假如right[0]应该放入left[3]，那么：①可以用一个var来保存right[0]，然后将left[3]之后的元素右移一次，再将var值放入left[3]；②也可以交换right[0]和left[3]的值，然后left[0]在新的位置向后遍历，找到合适的位置，再把前面的移位。 寻找合适位置的过程是一次插入排序，复杂度就是O(N2 * lgN)了。
- 另一个思路是，合并时，right数组向右找到第一个大于left当前元素的值，然后以块为单位交换。这个过程就类似于i am a student 转换为student a am i了。参考：原地归并排序。
代码：(以后补上，思路最重要)
算法题——归并排序的原地实现,布布扣,bubuko.com
算法题——归并排序的原地实现
原文：http://www.cnblogs.com/qieerbushejinshikelou/p/3920735.html
