百度软件研发笔试题
有一个递增数组，大小是10亿，将其分成很多小段，每段长度在20左右但是不一定，将段内的元素打乱，请问写一个效率最高的排序算法使算法重新是个递增数组，给出算法复杂度。
--------------------------------------------------------------
题目大概是这样的。
我的思路是，10亿能存在内存中，而一个元素偏离它正确的位置最多20个单位，使用二路归并排序就好。算法复杂度平均：
时间：O（nlogn）
空间：O（n）申请了一个等长的辅助数组
代码就不贴了，就是一般的归并，请问大家我这种方法是不是算法复杂度最低的算法，大家有没有更好的算法呢？
[解决办法]
每段长度在20左右但是不一定?左右是什么意思30算么？应该是以下吧？如果是的话
以前似乎有类似的题目，
思路是按40个分组，先把前40个排序，然后对20－60进行排序，以下类推排序，分段排序结束后整个排序就完成了，时间复杂度是O（n）
[解决办法]
不是的哦，对于局部有序的输入，插入排序的复杂度是O(n)哦。