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

��� ������� }

}

}