static
void
_merge(
int
*
src,
int
begin,
int
end);
int
merge_sort(
int
*
array,
int
begin,
int
end)
{
if
(array
==
NULL
||
begin
>
end)
return
0
;
int
mid
=
begin
+
(end
-
begin)
/
2
;
merge_sort(src,begin,mid);
merge_sort(src,mid
+
1
,end);
_merge(src,begin,end);
return 1;
}
static
void
_merge(
int
*
src,
int
begin,
int
end)
{
int
mid
=
begin
+
(end
-
begin)
/
2
;
int
b1
=
begin;
int
e1
=
mid;
int
b2
=
mid
+
1
;
int
e2
=
end;
int
*
dest
=
malloc(
sizeof
(
int
)
*
(end
-
begin
+
1
));
if
(dest
==
NULL)
return
;
int
i1;
int
i2;
int
i;
for
(i1
=
b1,i2
=
b2,i
=
begin;i1
<=
e1
&&
i2
<=
e2
&&
i
<=
end;
++
i){
if
(src[i1]
<
src[i2]){
dest[i
-
begin]
=
src[i1];
i1
++
;
}
else
{
dest[i
-
begin]
=
src[i2];
i2
++
;
}
}
for
(;i
<=
end
&&
i1
<=
e1;
++
i,
++
i1)
dest[i
-
begin]
=
src[i1];
for
(;i
<=
end
&&
i2
<=
e2;
++
i,
++
i2)
dest[i
-
begin]
=
src[i2];
for
(i
=
begin;i
<=
end;
++
i)
src[i]
=
dest[i
-
begin];
free(dest);
}
做一些小优化，只创建一次临时数组。
void _mergesort(int *array,int *tmp,int start,int end);
void mergesort(int *array,int len)
{
int i,*tmp;
if(array==NULL||len==0)
return;
tmp = (int*)malloc(sizeof(int)*len);
_mergesort(array,tmp,0,len-1);
free(tmp);
}
void _mergesort(int *array,int *tmp,int start,int end)
{
int mid = (start+end)/2;
int i,j,k;
if(start>=end)
return;
_mergesort(array,tmp,start,mid);
_mergesort(array,tmp,mid+1,end);
i = start;
j = mid+1;
for(k=start;k<=end&&i<=mid&&j<=end;++k){
if(array[i]<array[j]){
tmp[k] = array[i];
i++;
}else{
tmp[k]= array[j];
j++;
}
}
for(;i<=mid;++i)
tmp[k++]=array[i];
for(;j<=end;++j)
tmp[k++]=array[j];
memcpy(&array[start],&tmp[start],sizeof(int)*(end-start+1));
}