import java.util.*;

public class HW2part2
{

	public static void mergeSort(Comparable [ ] a)
	{
		Comparable[] tmp = new Comparable[a.length];
		mergeSort(a, tmp,  0,  a.length - 1);
	}


	private static void mergeSort(Comparable [ ] a, Comparable [ ] tmp, int left, int right)
	{
		if( left < right )
		{
			int center = (left + right) / 2;
			mergeSort(a, tmp, left, center);
			mergeSort(a, tmp, center + 1, right);
			merge(a, tmp, left, center + 1, right);
		}
	}


    private static void merge(Comparable[ ] a, Comparable[ ] tmp, int left, int right, int rightEnd )
    {
        int leftEnd = right - 1;
        int k = left;
        int num = rightEnd - left + 1;

        while(left <= leftEnd && right <= rightEnd)
            if(a[left].compareTo(a[right]) <= 0)
                tmp[k++] = a[left++];
            else
                tmp[k++] = a[right++];

        while(left <= leftEnd)    // Copy rest of first half
            tmp[k++] = a[left++];

        while(right <= rightEnd)  // Copy rest of right half
            tmp[k++] = a[right++];

        // Copy tmp back
        for(int i = 0; i < num; i++, rightEnd--)
            a[rightEnd] = tmp[rightEnd];
    }

    public static <E extends Comparable <E>> E max(E[] [] list){
    	int max = 0;
    	int saveI = 0;
    	int saveJ = 0;
    	for (int i = 0; i < list.length; i++){
    		for (int j = 0; j < list[i].length; j++)
    			if (max < ((Character) list[i][j])) {
    				max = (Character)list[i][j];
    				saveI = i;
    				saveJ = j;
    			}
    	}
    	return list[saveI][saveJ];
    }
    public static void main(String[] args)
    {
        System.out.println("Would you like 1 or 2 arrays?");
        int num = new Scanner(System.in).nextInt();
        if (num == 1 || num == 2){
	        if (num == 1){
	        	Character[] a = getMyArray();
	        }
	        if (num == 2){
	        	Character[] a = getMyArray();
	        	Character[] b = getMyArray();
	        	Character[][] c = {a,b};
	        	System.out.println(max(c));
	        }
        }else
        	System.out.println("Invalid amount of arrays. Restart Program.");
	}

    private static Character [] getMyArray(){
    	Scanner scan = new Scanner(System.in);
        ArrayList<Character> chArray = new ArrayList<Character>();
        System.out.println("Input a character for each line");
        while(true){
            System.out.print("> ");
            String input = scan.nextLine();
            if (input.equals(""))
            	break;
            Character save = input.charAt(0);
            if (save.equals(' '))
            	break;
            chArray.add(save);
        }
        Character[] converter = new Character[chArray.size()];
        converter = chArray.toArray(converter);
		mergeSort(converter);
		System.out.println(Arrays.toString(converter));
		return converter;
    }


 }