13 Sept 2013

Merge Sort 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.util.Arrays;

/**
 * MergeSort using recursive and non recursive calls (bottom up mergesort)
 * @author Prateek
 *
 */

public class MergeSort {
 int arr[];
 int size;
 
 public static void main(String[] args) {
 
  int []testInput={6,3,7,1,5,4,9,8,2};
  MergeSort m=new MergeSort();
  m.sort(testInput);
  
 }

 /**
  * 
  * @param values
  */
 public void sort(int values[]) {
 
  this.arr=values;
  this.size=arr.length;
  
  //TODO : uncomment if  recursive call required
  //mergeSort(0, size-1);  // recusive call
  
  bottomUpMergeSort();     // Non recursive call
  
  
  System.out.println("Sorted Array : " +Arrays.toString(arr));
 }

 /**
  * 
  * @param low
  * @param high
  */
 private void mergeSort(int low, int high) {
  
  if (low < high) {
   int mid = low + (high - low) / 2;
   
   mergeSort(low, mid);
   
   mergeSort(mid + 1, high);
   
   merge(low, mid, high);
  }
 }

 /**
  * Non recursive merge sort
  */
 private void bottomUpMergeSort()
 {
  // number of elements to be considered, and it doubles in the next pass
  for(int len=1;len<size ; len=len+len)
  {
   // for a given number of items traverse in pairs to call merge subroutine
   for(int index=0;index< size- len; index += len+len)
   {
    merge(index, index+len -1, Math.min(index + len + len -1 , size -1 ));
   }
  }
 }
 
 /**
  * Merge Subroutine 
  * @param low : lower index of the array
  * @param middle : Middle index of the array
  * @param high : Last index of the array to be sorted
  */
 private void merge(int low, int middle, int high) {

  int i=low; // initial index of 1st part of array
  int j=middle+1; // initial index of 2nd part of array
  
  int k=0;  // index for auxillay array
  
  int temp[]=new int[size]; //auxillay Array
  
  // Copying the smalller of the two elements int the two parts
  while(i<=middle && j<=high)
  {
   if(arr[i] < arr[j])
   {
    temp[k]=arr[i];
    i++;
   }
   else
   {
    temp[k]=arr[j];
    j++;
   }
   k++;
  }
  
  // simply 1st part of array copying if 2nd part gets exausted
  while(i<=middle)
  {
   temp[k]=arr[i];
   i++;
   k++;
  }
  
  // simply 2nd part of array copying if 1st part gets exausted
  while(j<=high)
  {
   temp[k]=arr[j];
   j++;
   k++;
  }

  // copying content from auxillay array to the original array
  k=0;
  while(low<=high)
  {
   arr[low]=temp[k];
   k++;
   low++;
  }
 }
}

Posted by @
Labels: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)