class BUMergeSort extends SortAlgorithm {	
	static int b[];
	
	void mergesort(int a[], int n) {
		int l, r = 0, m, N;
		for (N = 1; N < n; N *= 2) { 
			for (l = 0; l < n; l = r+1) {
				r = l + 2*N - 1;
				if (r > n) { 
					merge(a, l, l+N-1, n);
					if (l > 1) merge(a, l-2*N, l-1, n);
				}
				else 
					merge(a, l, l+N-1, r);
				pause();
			}
		}
	}
	
	void merge(int a[], int l, int m, int r) {
	    int i = l, j = m+1, k;
	    for (k = l; k <= r; k++) 
	        if (i > m) b[k] = a[j++]; else 
	        if (j > r) b[k] = a[i++]; else
		  	b[k] = a[i] < a[j] ? a[i++] : a[j++];
	    for (k = l; k <= r; k++) a[k] = b[k];	    
	} 

    void sort(int a[]) {
    	b = new int[a.length];
    	mergesort(a, a.length-1);
	}
}