MergeSort implementation with java.util.List passed as argument, not returned 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 &lt;E extends Comparable&lt;E&gt;&gt; void sort(List&lt;E&gt; list) {
        final int length = list.size();
        List&lt;E&gt; left = null;
        List&lt;E&gt; right = null;
        if (length == 1 || length == 0) {
            return;
        } else {
            left = new ArrayList&lt;&gt;(list.subList(0, length/2));
            right = new ArrayList&lt;&gt;(list.subList(length/2, length));
            sort(left);
            sort(right);            
        }       
        // can these be improved?
        list.clear(); 
        list.addAll(merge(right, left));
    }

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

        // add remaining
        while (leftIndex &lt; left.size()) {
            newList.add(left.get(leftIndex));
            leftIndex++;
        }           
        while (rightIndex &lt; 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?
You could do

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


with

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


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