import java.util.Comparator;

/**
 * A merge sort implementation
 * @author gtowell
 * created: April 15, 2020
 */
@SuppressWarnings("unchecked")
public class MergeObj<K> {
    
    /**
     * Merge the two lists
     * @param list1 the first list, sorted
     * @param list2 the second list, sorted
     * @return a new list (array) containing all of the eleents of lsist1 and list2, sorted.
     */
    private K[] domerge(K[] list1, K[] list2, Comparator<K> c)
    {
        K[] rtn = (K[])new Object[list1.length + list2.length];
        int locr=0, loc1=0, loc2=0;
        while (loc1<list1.length && loc2<list2.length) 
        {
            if (c.compare(list1[loc1],list2[loc2]) < 0)
            {
                rtn[locr++]=list2[loc2++];
            }
            else
            rtn[locr++]=list1[loc1++];
        }
        for (int i=loc1; i<list1.length; i++)
        rtn[locr++]=list1[i];
        for (int i=loc2; i<list2.length; i++)
        rtn[locr++]=list2[i];
        return rtn;
    }
    
    public void sortInPlace(K[] list, Comparator<K> c) {
        K[] aa = doMergeSort(list, 0, list.length-1, c);
        // change the contents of the provided array
        for (int i=0; i<list.length; i++)
            list[i]=aa[i];
    }
    
    /**
     * The internal, recursive implementation of merge sort
     */
    private K[] doMergeSort(K[] list, int strt, int eend, Comparator<K> c) {
        if (eend==strt)
        {
            K[] tmp = (K[])new Object[1];
            tmp[0]=list[strt];
            return tmp;
        }
        if (eend<strt)
            return (K[])new Object[0];
        int mid = (strt+eend)/2;
        return domerge(doMergeSort(list, strt, mid, c), doMergeSort(list, mid+1, eend, c), c);
    }
    
    public static void main(String[] args) {
        Student[] sss = Student.getStudents();
        
        for (Student s : sss) {
            System.out.println(s);
        }   
        MergeObj<Student> mos = new MergeObj<>();
        mos.sortInPlace(sss, Student.nameComparator());
        mos.sortInPlace(sss, Student.yearComparator());

        System.out.println();
        for (Student s : sss) {
            System.out.println(s);
        }
    

}
   
}