This is the Merge Sort algorithm that we will disucss in class. Please print it out and spend some time working through it - you should understand what this does and how it does it! Please take a print out of this code with you to class for lecture 25 (Recursion).
public class MS {
public static void main(String[] args) {
� 牋牋牋牋� int[] test1 = { 13, 26, 12, 14, 23, 25, 10, 24, 11, 19, 17, 18, 16, 20, 22, 21, 15 } ;
� 牋牋牋牋� MS.mergeSort(test1,0,test1.length-1);
� 牋牋牋牋� MS.print("sorted", test1);
}
public static void print(String s, int[] a) {
� 牋牋牋牋� System.out.print(s);
� 牋牋牋牋� for (int i =0; i < a.length; i++)
牋牋牋 牋牋牋牋牋牋牋牋 System.out.print(" "+a[i]);
� 牋牋牋牋� System.out.println() ;
}
public static void mergeSort(int[] anArray, int first, int last) {
� 牋牋牋牋� int size = (last - first) + 1 ;
� 牋牋牋牋� if ( size > 1) {
牋牋 牋牋牋牋牋牋牋牋牋 int frontsize = size/2 ;
牋牋 牋牋牋牋牋牋牋牋牋 int backsize = size - frontsize ;
牋牋 牋牋牋牋牋牋牋牋牋 int[] front = new int[frontsize] ;
牋牋 牋牋牋牋牋牋牋牋牋 int[] back� = new int[backsize] ;
牋牋 牋牋牋牋牋牋牋牋牋 int i;
牋牋 牋牋牋牋牋牋牋牋牋 for (i=0; i < frontsize; i++)
牋牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋 front[i] = anArray[first + i] ;
牋牋 牋牋牋牋牋牋牋牋牋 for (i=0; i < backsize;� i++)
牋牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋 back[i]� = anArray[first + frontsize + i] ;
牋牋 牋牋牋牋牋牋牋牋牋 MS.mergeSort(front,0,frontsize-1);
牋牋 牋牋牋牋牋牋牋牋牋 MS.mergeSort(back, 0,backsize -1);
牋牋 牋牋牋牋牋牋牋牋牋 MS.merge(front,back,anArray,first,last) ;
� 牋牋牋牋� }
}
public static void merge(int[] front, int[] back, int[] anArray, int first, int last) {
牋� 牋牋牋� int fIndex = 0 ; // front index
牋� 牋牋牋� int bIndex =0 ;� // back� index
牋� 牋牋牋� int i = first ;牋� // index in anArray in which to place next element
牋�
牋� 牋牋牋� while (( fIndex < front.length) && (bIndex < back.length)) {
牋牋牋 牋牋牋牋牋牋牋牋 if (front[fIndex] < back[bIndex]) {
牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 anArray[i] = front[fIndex] ;
牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 i++ ;
牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 fIndex++ ;
牋牋牋 牋牋牋牋牋牋牋牋 }
牋牋牋 牋牋牋牋牋牋牋牋 else {
牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 anArray[i] = back[bIndex] ;
牋牋牋牋 牋牋牋牋牋牋牋牋牋牋牋牋牋 i++ ;
� 牋牋牋�牋牋牋牋牋牋牋牋牋牋牋牋牋 bIndex++ ;
牋牋牋 牋牋牋牋牋牋牋牋 }
牋� 牋牋牋� }
牋牋
牋� 牋牋牋� while ( fIndex < front.length) {
牋牋牋牋 牋牋牋牋牋牋牋 anArray[i] = front[fIndex] ;
牋牋牋牋 牋牋牋牋牋牋牋 i++ ;
牋牋牋牋 牋牋牋牋牋牋牋 fIndex++ ;
牋� 牋牋牋� }
牋牋
牋� 牋牋牋� while ( bIndex < back.length) {
牋牋牋牋 牋牋牋牋牋牋牋 anArray[i] = back[bIndex] ;
牋牋 牋牋牋牋牋牋牋牋牋 i++ ;
牋牋牋牋 牋牋牋牋牋牋牋 bIndex++ ;
牋� 牋牋牋� }
}
}