返回信息流对一个数组分成[start,mid],[mid+1,end]两部分，且分别有序。那么在merge两个有序的部分时，要求在O（1）的空间复杂度内
完成，我搜到的策略好像是对 数组的后半部分里的每一个元素j，找到一个合适的插入位置P,然后(p,j-1]每个元素往后挪动一个。
感觉有点类似与插入排序的意思。那么这种情况下的时间复杂度，岂不是O(（n／2）^2)了？那么总体上，归并排序的时间复杂度是不是也变大了？不再是O(nlog)?请大佬们指教一下啊
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #96581同步于 2018/9/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
归并排序Merge操作O(1)空间复杂度完成
gauze
2018/9/19镜像同步1 回复
订阅后，新回复会通过你的通知中心匿名送达。
1 条回复
我大概想了一个不需要插入后挪动过多元素的方案，如有问题还请指正。
针对目前的两部分数组，队头分别为start 和mid+1,如果start更小将左侧对头后移，如果start表示的元素更大，将其与mid+1元素交换，此时左侧队头在mid+1, 右侧队头在mid + 2,继续比较队头元素。
如果左侧队头较小，将mid + 1元素与start + 1元素交换，左右侧队头都不变，但是记录当前已经排序了的指针位置+1了
如果右侧队头较小，将mid + 2元素与start + 1元素交换，右侧队头右移。
这样直到[start,mid]元素就位，递归排序[mid+1,end]部分,右侧队头表示新的mid + 1。因为每次移动都能够确定一个元素的正确位置，并且只交换常数次元素，因此虽然有递归在里面，整体还是O(n)吧