算法-合并排序

/* Function to merge the subarrays of a[] */voidmerge(inta[], intbeg, intmid, intend)    
{    
inti, j, k;  
intn1=mid-beg+1;    
intn2=end-mid;    
intLeftArray[n1], RightArray[n2]; //temporary arrays  /* copy data to temp arrays */for (inti=0; i<n1; i++)    
LeftArray[i] =a[beg+i];    
for (intj=0; j<n2; j++)    
RightArray[j] =a[mid+1+j];    
i=0, /* initial index of first sub-array */j=0; /* initial index of second sub-array */k=beg;  /* initial index of merged sub-array */while (i<n1&&j<n2)    
    {    
if(LeftArray[i] <=RightArray[j])    
        {    
a[k] =LeftArray[i];    
i++;    
        }    
else        {    
a[k] =RightArray[j];    
j++;    
        }    
k++;    
    }    
while (i<n1)    
    {    
a[k] =LeftArray[i];    
i++;    
k++;    
    }    
while (j<n2)    
    {    
a[k] =RightArray[j];    
j++;    
k++;    
    }    
}

classMerge {  
/* Function to merge the subarrays of a[] */voidmerge(inta[], intbeg, intmid, intend)    
{    
inti, j, k;  
intn1=mid-beg+1;    
intn2=end-mid;    
/* temporary Arrays */intLeftArray[] =newint[n1];  
intRightArray[] =newint[n2];  
/* copy data to temp arrays */for (i=0; i<n1; i++)    
LeftArray[i] =a[beg+i];    
for (j=0; j<n2; j++)    
RightArray[j] =a[mid+1+j];    
i=0; /* initial index of first sub-array */j=0; /* initial index of second sub-array */k=beg;  /* initial index of merged sub-array */while (i<n1&&j<n2)    
    {    
if(LeftArray[i] <=RightArray[j])    
        {    
a[k] =LeftArray[i];    
i++;    
        }    
else        {    
a[k] =RightArray[j];    
j++;    
        }    
k++;    
    }    
while (i<n1)    
    {    
a[k] =LeftArray[i];    
i++;    
k++;    
    }    
while (j<n2)    
    {    
a[k] =RightArray[j];    
j++;    
k++;    
    }    
}    
voidmergeSort(inta[], intbeg, intend)  
{  
if (beg<end)   
    {  
intmid= (beg+end) /2;  
mergeSort(a, beg, mid);  
mergeSort(a, mid+1, end);  
merge(a, beg, mid, end);  
    }  
}  
/* Function to print the array */voidprintArray(inta[], intn)  
{  
inti;  
for (i=0; i<n; i++)  
System.out.print(a[i] +" ");  
}  
publicstaticvoidmain(Stringargs[])  
{  
inta[] = { 11, 30, 24, 7, 31, 16, 39, 41 };  
intn=a.length;  
Mergem1=newMerge();  
System.out.println("\nBefore sorting array elements are - ");  
m1.printArray(a, n);  
m1.mergeSort(a, 0, n-1);  
System.out.println("\nAfter sorting array elements are - ");  
m1.printArray(a, n);  
System.out.println("");  
}  
  }