Monday 15 October 2012

Merge Sorting



public class mergeSort {

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  mergeSort test = new mergeSort();
 }
 private int[] array;
 private int N;
 public mergeSort(){
  N = 10;
  array = new int[N];
  for(int i=0;i<array.length;i++)
   array[i] = (int)(Math.random()*10)+1;
  print(array);
  sort(array,0,N-1);
  print(array);
 }
 public void print(int []array){
  for(int i = 0;i<array.length;i++)
   System.out.print(array[i]+", ");
  System.out.println("");
 }
 public void sort(int []array,int p,int r){
  if(r-p>=1)
  {
   int q = (int)(Math.floor((double)((p+r)/2)));
   sort(array,p,q);
   sort(array,q+1,r);
   merge(array,p,q,r);
  } 
   
 }
 public void merge(int []array,int p,int q,int r){
  int n1 = q-p+1;
  int n2 = r-q;
  int left[] = new int[n1+1];
  int right[] = new int[n2+1];
  for(int i = 0;i<left.length-1;i++)
   left[i] = array[p+i];
  for(int i=0;i<right.length-1;i++)
   right[i] = array[q+i+1];
  left[n1] = 11;
  right[n2] = 11;
  int i = 0;
  int j = 0;
  for(int k = p;k<=r;k++){
   if(left[i]<=right[j]){
    array[k] = left[i];
    i++;
   }else{
    array[k] = right[j];
    j++;
   }
  }
  
 }
}

No comments:

Post a Comment