public class Sort {
    
    //================================= sort =================================
    //
    // Input: array A of XYPoints refs 
    //        lessThan is the function used to compare points
    //
    // Output: Upon completion, array A is sorted in nondecreasing order
    //         by lessThan.
    //=========================================================================
    
    public static void msort(XYPoint[] A, Comparator lessThan)
    {
	XYPoint[] temp = new XYPoint[A.length];
	mergeSort(A, temp, 0, A.length - 1, lessThan); 
    }
    
    //============================= mergeSort ==============================
    //
    // Input: array of XYPoints refs A 
    //        array temp used for the merging
    //        integers l and r
    //        lessThan is the function used to compare points
    //
    // Output: Upon completion, the portion of the array A from A[l] to A[r] 
    //         is sorted in nondecreasing order by lessThan
    //=======================================================================
    
    static void mergeSort(XYPoint[] A,
			  XYPoint[] temp,
			  int l, int r,
			  Comparator lessThan) 
    {
	int srcLeft;    // index of current location in left half of A
	int srcRight;   // index of current location in right half of A
	int dst;        // index of current location in temp array
	int mid;        // index of the last element of the left half of A
	
	if (l == r) return;
	
	mid = (l + r)/2;                        // find the middle
	mergeSort(A, temp, l, mid, lessThan);   // recursively sort left half
	mergeSort(A, temp, mid+1, r, lessThan); // recursively sort right half
	
	//  Now merge the 2 halves of A, until reaching the end of one
	
	srcLeft = dst = l;
	srcRight = mid + 1;
	while (srcLeft <= mid && srcRight <= r)
	    {
		if (lessThan.comp(A[srcLeft], A[srcRight]))
		    {
			temp[dst] = A[srcLeft]; srcLeft++;
		    }
		else 
		    {
			temp[dst] = A[srcRight]; srcRight++; 
		    }
		dst++; 
	    }
	
	// If there are any elements from the left half, copy them to
	// the temp array.
	while (srcLeft <= mid) 
	    {
		temp[dst] = A[srcLeft]; srcLeft++; dst++;
	    }
	
	// Now copy temp elements back into A (except those that we know are
	// already there).
	for (int j = l; j < srcRight; j++)
	    A[j] = temp[j];
    }
}