Steven R. Brandt

package sortlab;

public interface Sorter {
    /**
     * Generate an array of random numbers.
     * First, instantiate a variable of type
     * Random (from the java.util package)
     * using the seed provided.
     * Next, allocate an array of the specified size.
     * Finally, fill the array with random
     * numbers using the Random varaible you
     * instantiated. Values should be between
     0 and 9999 inclusive.
     *
     * @see <a href="https://docs.oracle.com/javase/8/docs/api/java/util/Random.html">java.util.Random</a>
     */
    int[] generateRandArray(int size,int seed);

    /**
     * Create a copy of a sub array.
     * Copy the values of array arr beginning
     * with start up to (but not including) end.
     * The number of values in the returned array
     * should be equal to (end-start).
     */
    int[] subArray(int [] arr,int start, int end);

    /**
     * Given two arrays, ar1, and ar2,
     * both of which are sorted, merge
     * the two of them into a single
     * sorted array.
     * To do this,
     *
     * First, instantiate an array big enough
     * to hold all the values in ar1 and ar2. Name
     * it ar3.
     *
     * Next, declare three variables, index1 (for ar1),
     * index2 (for ar2), and index3 (for ar3),
     * each starting with value zero.
     *
     * Next, create a while loop that will iterate as
     * long as index1 is valid for ar1, and index2
     * is valid for ar2.
     *
     * Inside the while loop, determine which array
     * (ar1 or ar2) has the smallest value at its
     * index (index1 or index2) an copy that into
     * ar3 iat its index position. Increment the index
     * for ar3 and the array you copied from.
     *
     * Create a while loop that copies any remaining
     * values from ar1 to ar3.
     *
     * Create a while loop that copies any remaining
     * values from ar2 to ar3.
     *
     * Example of what Merge should do:
     * given ar1=[1,3,5] and
     * ar2=[2,4] merge to ar3=[1,2,3,4,5].
     */
    int[] mergeArrays(int[] ar1,int[] ar2);

    /**
     * Create a new array with the same
     * values as ar, but sorted. It should
     * work as follows
     * 1) If the array is size 1 or less,
     *    return a copy of the array.
     * 2) Create two arrays using subArray().
     *    Each should contain approximately
     *    half the values in ar. If
     *    the array is odd-sized, one of the
     *    two halves will be 1 bigger than
     *    the other. Example: if ar=[1,5,3,2,4]
     *    then ar1=[1,5,3] and ar2=[2,4].
     * 3) Call sort on each of the two arrays
     *    created in step two.
     * 4) Return the result of merging the
     *    two sorted arrays from step 3.
     */
    int[] sort(int[] ar);
}

package sortlab;

import java.util.List;

public interface SorterL {
    /**
     * Generate a list of random numbers.
     * Use the seed to set the seed of the
     * java.util.Random class, and generate
     * a list of length size. Random numbers
     * should be between 0 and 9999 inclusive.
     *
     * We could have used Integer here. However,
     * both Integer and String implement Comparable,
     * so this allows us to use this class for
     * both of those object types using the "compareTo()"
     * method.
     */
    List<Comparable> generateRandList(int size,int seed);

    /**
     * Create a copy of a list subset.
     * Copy the values of array arr beginning
     * with start up to (but not including) end.
     * The number of values in the returned array
     * should be equal to (end-start).
     */
    List<Comparable> subList(List<Comparable> arr,int start, int end);

    /**
     * Given two lists, ar1, and ar2,
     * both of which are sorted, merge
     * the two of them into a single
     * sorted list. Example: [1,3,5] and
     * [2,4] merge to [1,2,3,4,5].
     *
     * Note that because we are using
     * Comparable lists here, we will not
     * compare with the <= operator. That
     * would not make sense if we had a string.
     * Instead, we will use the compareTo
     * method. It works like this:
     * <pre>
     * Comparable a1 = "Foo";
     * Comparable a2 = "Bar";
     * if( a1.compareTo(a2) < 0 ) {
     *   // This tests that a1 < a2
     * }
     */
    List<Comparable> mergeLists(List<Comparable> ar1,List<Comparable> ar2);

    /**
     * Create a new list with the same
     * values as ar, but sorted. It should
     * work as follows
     * 1) If the list is size 1 or less,
     *    return a copy of the list.
     * 2) Create two lists, each containing
     *    approximately half the values. If
     *    the list is odd-sized, one of the
     *    two halves will be 1 bigger than
     *    the other. Example: if ar=[1,5,3,2,4]
     *    then ar1=[1,5,3] and ar2=[2,4].
     * 3) Call sort on each of the two lists
     *    created in step two.
     * 4) Return the result of merging the
     *    two sorted lists from step 3.
     */
    List<Comparable> sort(List<Comparable> ar);
}