Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. import java.util.ArrayList;
  2. public class Array{
  3.  
  4.     public static void mergesort(ArrayList list){
  5.         if(list.size()-1>0){
  6.             int middle=list.size()/2;
  7.             ArrayList <Integer>leftList=new ArrayList();
  8.             ArrayList <Integer>rightList=new ArrayList();
  9.  
  10.             divide(list,leftList,rightList);//divide list into two array - left 'n' right
  11.  
  12.             mergesort(leftList);//recursive for left side
  13.             mergesort(rightList);//recursive for right side
  14.  
  15.             merge(list,leftList,rightList);//merge
  16.         }
  17.     }
  18.  
  19.     public static void divide(ArrayList list,ArrayList leftList,ArrayList rightList){
  20.         int middle=list.size()/2;
  21.         int left=0,right=0;
  22.         for(int i=0;i<middle;i++){//left side array
  23.             leftList.add(i,list.get(i));
  24.         }
  25.         for(int i=middle;i<list.size();i++){//right side array
  26.             rightList.add(i-middle,list.get(i));
  27.         }
  28.     }
  29.  
  30.     public static  void merge(ArrayList list,ArrayList <Integer>leftList,ArrayList <Integer>rightList){
  31.         int left=0;int right=0;
  32.         for(int i=0;left<leftList.size()&&right<rightList.size();i++){//copy left n right into list - increasing order
  33.             int l=leftList.get(left);
  34.             int r=rightList.get(right);
  35.             list.remove(i);
  36.             if(l>r){
  37.                 list.add(i,rightList.get(right));
  38.                 right++;
  39.             }
  40.             else{
  41.                 list.add(i,leftList.get(left));
  42.                 left++;
  43.             }
  44.            
  45.         }
  46.         for(int i=left;i<leftList.size();i++){//copy the rest of left into list
  47.             list.remove(i+right);
  48.             list.add(i+right,leftList.get(i));
  49.            
  50.         }
  51.         for(int i=right;i<rightList.size();i++){//copy the rest of right into list
  52.             list.remove(i+left);
  53.             list.add(i+left,rightList.get(i));
  54.            
  55.         }
  56.  
  57.     }
  58.     static public String display(ArrayList list){
  59.         String str="["+list.get(0);
  60.         for(int i=1;i<list.size();i++){
  61.             str+=","+list.get(i);
  62.         }
  63.         str+="]";
  64.         return str;
  65.     }
  66. }