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++ ;

}

}

}