MergeImpl

package com.liuxt.sort.impl;

import com.liuxt.sort.Sort;

public class MergeImpl implements Sort {

 /*  * 归并排序的算法：  *   *  (non-Javadoc)  * @see com.liuxt.sort.Sort#sortData(int[])  */ public void sortData(int[] data1) {  int length=1,k=0; /**length为分段大小，最开始设置为1**/  int n=data1.length;    int[] data2;  data2=new int[n];    while(length<n)  {   if(k==0) Msort(data1,data2,n,length);   else Msort(data2,data1,n,length);   length*=2; /**每完成一趟归并，所有的有序分段的长度翻一倍**/   k=1-k;  }  if(k==1) /**归并结果为基数，排序结果放在data2中，再将结果复制到data1中**/  for(k=0;k<n;++k)   data1[k]=data2[k];   }

 /**  * 函数的功能：  *   将data1中相邻的两个分段合并为一个有序段，归并的结果放在data2中。  *   data1中的分段情况如下：  *   data1[0...len-1],data1[len....2*len-1],,,data1[(I-1)*len...I*len-1]  *   I为分组号  *     *   * @param data1  * @param data2  * @param n  * @param len  */ private void Msort(int[] data1, int[] data2, int n, int len) {  int start_p,end_p;  start_p=0; /**从下标为0的元素开始，**/  while(start_p+len<n){ /**取相邻的两个有序段开始合并**/   end_p=start_p+2*len-1;   if(end_p>=n) end_p=n-1;   /**调用合并函数。开始，start_p=0,len=1,end_p=1    两两合并为一个有序段，结果存在data2中 **/   Merge(data1,data2,start_p,start_p+len-1,end_p);    start_p=end_p+1;  }  if(start_p<n){   /**直接将剩下的一个有序段的元素复制到data2中。**/   for(;start_p<n;start_p++)    data2[start_p]=data1[start_p];  } }

 /**  * 将分别有序的data1[s,,m]和data1[m+1..n]归并为有序的data2[s...n]  *   * @param data1  * @param data2  * @param s  * @param m  * @param n  */ private void Merge(int[] data1, int[] data2, int s, int m, int n) {  int i,j,k;  for(i=m+1,k=s;s<=m && i<=n;++k)  {   if(data1[s]<data1[i])     data2[k]=data1[s++];   else data2[k]=data1[i++];  }  for(j=s;j<=m;++j,++k)   data2[k]=data1[j];  for(j=i;j<=n;++j,++k)   data2[k]=data1[j]; }}