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];
 }
}