import java.util.Arrays;

class Recursion {

    public static void mergeSort(char[] A) {
	// if A has length 1, then done.
	if (A.length > 1) {
	    // split into two halves, recursively sort, and then merge.

	    // middle is the last entry in the left-hand side.
	    int middle = (A.length-1)/2;
	    char[] left = new char[middle+1];
	    char[] right = new char[A.length - (middle+1)];

	    for (int i = 0; i < middle+1; i++) {
		left[i] = A[i];
	    }
	    
	    int rightIndex = 0;
	    for (int i = middle+1; i < A.length; i++) {
		right[rightIndex] = A[i];
		rightIndex++;
	    }

	    mergeSort(left);
	    mergeSort(right);

	    merge(A,left,right);
	}

    }
    
    // Only call this when result.length = B.length + C.length!!!
    private static void merge(char[] result, char[] B, char[] C) {
	int a = 0; // next available slot of result
	int b = 0; // next available slot of B (smallest remaining element)
	int c = 0; // next available slot of C (smallest remaining element)

	while(a < result.length) { 
	    //	    if (B is not empty) {
	    //		if (C is empty) {
	    //              do the "then" 
	    // 		} else {
	    // 		    do whichever is appropriate
	    // 		}
	    // 	    } else {
	    // 		do the "else"
	    // 	    }
	    if ((b < B.length) 
		&& (!(c < C.length) || B[b] < C[c])) {
		result[a] = B[b];
		a++;
		b++;
	    } else {
		result[a] = C[c];
		a++;
		c++;
	    }
	}
    }

    public static boolean isPalindrome(String text) {
	int n = text.length();

	if (n == 0 || n == 1) {
	    return true;
	}
	if (!Character.isLetter(text.charAt(0))) {
	    String innards = text.substring(1,n);
	    return isPalindrome(innards);
	}
	if (!Character.isLetter(text.charAt(n-1))) {
	    String innards = text.substring(0,n-1);
	    return isPalindrome(innards);
	}

	// if the first character matches the last character,
	// then check the innards.  otherwise return false.
	if (text.charAt(0) == text.charAt(n-1)) {
	    String innards = text.substring(1,n-1);
	    return isPalindrome(innards);
	} else {
	    return false;
	}
    }

    public static void main(String[] args) {
	char[] text = "HAPPY KIDS ARE SMILING KIDS".toCharArray();
	System.out.println(Arrays.toString(text));
	mergeSort(text);
	System.out.println(Arrays.toString(text));
	System.out.println(isPalindrome("AMANAPLANACANALPANAMA"));
	System.out.println(isPalindrome("GO HANG A SALAMI I'M A LASAGNA HOG"));
	System.out.println(isPalindrome("SIT ON A POTATO PAN,      OTIS"));
	System.out.println(isPalindrome("DOC, NOTE:  I DISSENT.  A FAST NEVER PREVENTS A FATNESS.  I DIET ON COD!"));
    }

}