归并排序算法问题 c 语言实现

[SlientHunter]

我在网上查了一下归并排序算法，都需要分配一个新的数组，下面是我考虑的代码（不分配新的数组），不知道这样是否可行，效率如何，希望得到指点。

void mergsort(int v[], int left, int right){
int i, j, k, middle, temp;

if((right-left) < 2){
if(v[left] > v[right]){
temp = v[left];
v[left] = v[right];
v[right] = temp;
}
return;
}
middle = (left + right) / 2;
mergsort(v, left, middle);
mergsort(v, middle+1, right);
for(i=left, j=middle+1;j<=right;j++){
if(v[i] >= v[j]){
temp =v[j];
k = j;
while(k > i){
v[k] = v[k-1];
k--;
}
v[k]= temp;
i++;
}
}
}

[Jaylee]

逼格不够高

[SlientHunter]

@Jaylee 不懂啥意思

[nolouch]

你合并那段，本来O(N)解决的，你又来了次O(N*N)的插入排序，，，还不去直接插入排序了呢。
@SlientHunter

[jiang42]

有错误吧－。－
mergesort([1], 0, 0)应该会出bug

[jiang42]

看错了，没问题

[heliumhgy]

并归排序本来就不是in place的

[msg7086]

不肯给空间，就多花时间。

[xylophone21]

这个接口定义看的很是醉人啊