import java.util.ArrayList;

public class Mergesort {

    /**
     * Sorts list given using the mergesort algorithm
     * @param list the list to be sorted
     * @param first the index of the first element of the list to be sorted
     * @param last the index of the last element of the list to be sorted
     */
    public static void mergesort(ArrayList<Comparable> list, int first, int last){
       if (last - first == 1)
       {
    	   if(list.get(first).compareTo(list.get(last)) > 0)
    	   {
    		   Comparable temp = list.get(first);
    		   list.set(first, list.get(last));
    		   list.set(last, temp);
    	   }
       }

    }


    /**
     * Merges two ordered sublists.
     *
     * PRE-CONDITION: list from first to mid-1 is in order, list from mid to last is in order
     * POST-CONDITION: list from first to last is in order
     *
     * @param list the list containing the ordered sublist
     * @param first first element of the first sublist
     * @param mid first element of the second sublist
     * @param last last element of the second sublist
     */
    public static void merge(ArrayList<Comparable> list, int first, int mid, int last){

    }

    public static void main(String[] args) {

    }


    //================================================
    //======= HELPER METHODS FOR TESTING BELOW =======
    //================================================


    /**
     * Returns true if two lists have the same elements.
     *
     * @param orig the original list
     * @param copy the copy of the list
     *
     * @return true if orig and copy have the same number of each element, false otherwise
     */
    private static boolean sameElements(ArrayList<Comparable> orig, ArrayList<Comparable> copy){

    }

    /**
     * Returns true if list is in ascending order
     *
     * @param list the list to check for ordering
     *
     * @return true if list is in ascending order, false otherwise
     */
    private static boolean inOrder(ArrayList<Comparable> list){

    }

    /**
     * Returns a deep copy of the given list
     *
     * @param list the list to be copied and return
     *
     * @return deep copy of argument list
     */
    private static ArrayList<Comparable> copyList(ArrayList<Comparable> list){

    }

    /**
     * Returns a list of Strings
     *
     * @param length the number of elements the list is to have
     *
     * @return a list of String elements with length size
     */
    private static ArrayList<Comparable> listOfStrings(int length){

    }

    /**
     * Returns a list of Integers
     *
     * @param low the minimum number in the range of elements
     * @param high the maximum number in the range of elements
     * @param length the number of elements the list is to have
     *
     * @return a list of Integer elements with length size
     */
    private static ArrayList<Comparable> listOfInts(int low, int high, int length){

    }

}