public class MergeSort { |
|
public static void mergeSort(Comparable[]a) |
{ |
Comparable[]b= new Comparable[a.length]; |
int s= 1 ; |
while (s<a.length) |
{ |
mergePass(a,b,s); //合并到数组b |
s+=s; |
mergePass(b,a,s); //合并到数组a |
s+=s; |
} |
} |
private static void mergePass(Comparable[] x, Comparable[] y, int s) |
{ //合并大小为s的相邻数组 |
int i= 0 ; |
while (i<=x.length- 2 *s) |
{ //合并大小为s的两端相邻字数组 |
merge(x,y,i,i+s- 1 ,i+s* 2 - 1 ); |
i=i+ 2 *s; |
} |
//剩下的元素个数小于2s |
if (i+s<x.length) |
{ |
merge(x, y, i, i+s- 1 , x.length- 1 ); |
} |
else //复制到y |
{ |
for ( int j = i; j < x.length; j++) |
{ |
y[j] = x[j]; |
} |
} |
} |
private static void merge(Comparable[] c, Comparable[] d, int l, int m, int r) |
{ |
//合并c[l:m]和c[m+1,r]到d[l:r] |
int i= 1 , j=m+ 1 ,k=l; |
while (i<=m && j<=r) |
{ |
if (c[i].compareTo(c[j])<= 0 ) |
{ |
d[k++]=c[i++]; |
} |
else |
{ |
d[k++]=c[j++]; |
} |
} |
|
if (i>m) |
{ |
for ( int k2 = 0 ; k2 <=r; k2++) |
{ |
d[k++] = c[k2]; |
} |
} |
else |
{ |
for ( int k2 = 0 ; k2 <=m; k2++) |
{ |
d[k++] = c[k2]; |
} |
} |
} |
} |