This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Wednesday, 24 December 2014

Merge Sort

package sorting;

public class MergeSort {

 public static void main(String[] args) { 
  new MergeSort();
 }

 public MergeSort() {
  int[] arr=new int[]{6,1,4,2,3,5,10,2,2,1,6};

  System.out.println("Before Sorting...");
  printArray(arr);
  System.out.println();
  mergeSort(arr, 0, arr.length-1);
  System.out.println("After Sorting...");
  printArray(arr);

 }

 private void mergeSort(int[] arr, int low, int high) {
  if (low < high) {
   int middle = low + (high - low) / 2;
   mergeSort(arr, low, middle);
   mergeSort(arr, middle + 1, high);
   merge(arr,low, middle, high);
  }
 }

 private void merge(int arr[], int start, int mid, int end){
  int i=start,j=mid+1;
  int count=0;
  int tmp[]=new int[end-start+1];
  while(i<=mid && j<=end){
   if(arr[i]<arr[j]){
    tmp[count]=arr[i];
    i++;
   }else{
    tmp[count]=arr[j];
    j++;
   }
   count++;
  }

  while(i<=mid){
   tmp[count]=arr[i];
   count++;
   i++;
  }

  while(j<=end){
   tmp[count]=arr[j];
   count++;
   j++;
  }

  for (int k = 0; k < tmp.length; k++) {
   arr[start+k]=tmp[k];
  }
 }

 private void printArray(int arr[]){
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }
}

No comments:

Post a Comment