MergeSort implementation with java.util.List passed as argument, not returned

Question

I'm working on an implementation of MergeSort which sorts a List given as an argument. As follows

public class MergeSort implements Sort {
    @Override
    public <E extends Comparable<E>> void sort(List<E> list) {
        final int length = list.size();
        List<E> left = null;
        List<E> right = null;
        if (length == 1 || length == 0) {
            return;
        } else {
            left = new ArrayList<>(list.subList(0, length/2));
            right = new ArrayList<>(list.subList(length/2, length));
            sort(left);
            sort(right);            
        }       
        // can these be improved?
        list.clear(); 
        list.addAll(merge(right, left));
    }

    private <E extends Comparable<E>> List<E> merge(List<E> right, List<E> left) {
        List<E> newList = new LinkedList<>();
        int rightIndex = 0, leftIndex = 0;
        while (rightIndex < right.size() && leftIndex < left.size()) {
            E rightElement = right.get(rightIndex);
            E leftElement = left.get(leftIndex);
            if (rightElement.compareTo(leftElement) > 0) {
                newList.add(leftElement);
                leftIndex++;
            } else {
                newList.add(rightElement);
                rightIndex++;
            }
        }

        // add remaining
        while (leftIndex < left.size()) {
            newList.add(left.get(leftIndex));
            leftIndex++;
        }           
        while (rightIndex < right.size()) {
            newList.add(right.get(rightIndex));
            rightIndex++;
        }
        return newList;
    }
}

I want to do the sorting on the List that's passed as an argument, not return a new List. I feel, however, that calling clear() and addAll() a number of times might slow things down. How can I avoid these calls?

Answer 1

You could do

list.clear(); 
merge(right, left, list);

with

private static <E extends Comparable<E>> List<E> merge(List<E> source1, List<E> source2, List<E> destination) {
    // ...
    destination.add(element);
    // ...
}

The merge() function should be declared static to indicate that it doesn't use any instance variables.