import java.util.ArrayList;

归并排序是一种基于比较的排序算法，在多数的实现方法下它是稳定的。归并排序可是由计算机祖师级人物－冯 诺依曼提出的哦。

归并排序的过程：
1. 如果数据链表的长度为0或1，则返回
2. 将原始数据链表对半分成两个子链表
3. 对每个子链表递归的调用合并排序进行排序
4. 合并两个子链表使其成为一个排序完成的链表

归并排序的时间复杂度为О(nlogn)，空间复杂度为О(n)。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

 

public class Merge{
public List<Integer> mergesort(List<Integer> data){  
    if(data.size()<=1)  
          return data;  
    int middle = data.size()/2;  
    List<Integer> left = new ArrayList<Integer>();  
    List<Integer> right = new ArrayList<Integer>();  
    for(int i=0; i<middle; i++){  
          left.add(data.get(i));  
    }  
    for(int i=middle; i<data.size();i++){  
          right.add(data.get(i));  
    }  
    left = mergesort(left);  
    right = mergesort(right);  
    List<Integer> result = merge(left, right);  
    return result;  
} 
public List<Integer> merge(List<Integer> left, List<Integer> right){  
    List<Integer> result = new ArrayList<Integer>();  
    while(left.size()>0 && right.size()>0){  
          if(((Integer)left.get(0)).intValue()<=((Integer)right.get(0)).intValue()){  
                result.add(left.get(0));  
                left.remove(0);  
          } else{  
                result.add(right.get(0));  
                right.remove(0);  
          }  
    }  
    if(left.size()>0){  
          for(Iterator<Integer> iter = left.iterator(); iter.hasNext();){  
                result.add(iter.next());  
          }  
    }  
    if(right.size()>0){  
          for(Iterator<Integer> iter = right.iterator(); iter.hasNext();){  
                result.add(iter.next());  
          }  
    }  
    return result;  
} 
public int[] merge(int[] left,int[] right){  
    int result[] = new int[left.length + right.length];  
    int index = 0;//index of result  
    int x = 0;//index of left  
    int y = 0;//index of right   

    //compare each element in two arrays, after comparing, index++.  
    while(x<left.length && y<right.length){  
          if(left[x]<right[y]){  
                result[index++] = left[x++];  
          }else{  
                result[index++] = right[y++];  
          }  
    }  
     
    //the length of two arrays might be different,   
    //so we have to copy the rest elements in two arrays  
    while(x<left.length)    
          result[index++] = left[x++];    
    while(y<right.length)    
          result[index++] = right[y++];  
    return result;  
} 
public static void main(String[] args){
 Merge merge=new Merge();
 List<Integer> list=new ArrayList<Integer>();
 Random rand=new Random();
 for(int i=0;i<100;i++){
  int randnum=rand.nextInt(200);
  list.add(randnum);
 }
      List<Integer> result=merge.mergesort(list);
      for(Object o:result){
       int num=(Integer)o;
       System.out.println(num);}
 
}

}