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));?
}
???