Implement natural order comparator for non-comparable list

Question

I'm implementing the List interface for a clone of ArrayList. I'm trying to implement sort (source): I'm not sure how to implement the case where the comparator is null. My ArrayList does not extend Comparable because I want to be able to store non-comparable objects in the list. I've tried using the following for the sort method:

public void sort(Comparator<? super E> c){
    if(c == null){
        // Use ascending order
        class ascComparator<T extends Comparable<? super T>> implements Comparator<T> {
            public int compare(T a, T b) {
                return a.compareTo(b);
            }
        }
        c = new ascComparator<E>();
    }
    // Implementation of merge sort goes here
}

This expectedly gives an error as E does not extend Comparable. In the above documentation it is stated "if ... is null then all elements in this list must implement the Comparable interface". How do I check that the objects in the list implement Comparable and how do I then use compareTo without getting an error? Is there just a better way to do this?

Answer 1

To see what ArrayList does, try:

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        List<Object> objects = new ArrayList<>();
        objects.add(new Object());
        objects.add(new Object());

        objects.sort(null);
    }
}

Your comparator must just assume that the objects in the list are Comparable, that's the best it can do:

 class ascComparator implements Comparator<Object> {
            public int compare(Object a, Object b) {
                return ((Comparable)a).compareTo(b);
            }
        }

Which will throw a ClasscastException if the items in your list are not Comparable.