import java.awt.*;

public class MergeSort extends ShowSort {
	int piv=0;
	
	public static void main(String args[]) {
		MergeSort applet = new MergeSort();
		applet.launch("MergeSort");
	}

	void doSort() {
		inplace_dir = false;
		inplace_pos = 0;
		mergeSort(array, 0, NUM-1);
	}

	void mergeSort(int array[], int bottom, int top) {
		int t, mid;

		if (bottom>=top)
			return;
		
		mid=(bottom+top)/2;
		
		mergeSort(array,bottom,mid);
		mergeSort(array,mid+1,top);
		inplace_pos=mid;
		merge(array,bottom,mid,mid+1,top);
	}

	void merge(int array[], int b1, int t1, int b2, int t2) {
		int i,pos1,pos2,fpos;

		int len1=(t1-b1+1);
		int len2=(t2-b2+1);
		
		int half1[] = new int[len1];
		int half2[] = new int[len2];

		curr_bar_color=Color.green;
		
		for(i=0; i<len1; i++) {
			half1[i] = array[i+b1];
			swapped(i+b1);
		}
		for(i=0; i<len2; i++) {
			half2[i] = array[i+b2];
			swapped(i+b2);
		}

		curr_bar_color=Color.magenta;
		
		pos1 = pos2 = 0;
		fpos=b1;
		
		while(pos1 < len1 && pos2 < len2) {
			compared(b1+pos1);
			if(half1[pos1] > half2[pos2]) {
				array[fpos] = half2[pos2++];
				swapped(fpos++);
			} else {
				array[fpos] = half1[pos1++];
				swapped(fpos++);
			}
		}

		curr_bar_color=Color.red;
		while(pos1 < len1) {
			array[fpos] = half1[pos1++];
			swapped(fpos++);
		}

		while(pos2 < len2) {
			array[fpos] = half2[pos2++];
			swapped(fpos++);
		}
	}
}