I'm working on an implementation of MergeSort which sorts a List given as an argument. As followspublic 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?
MergeSort implementation with java.util.List passed as argument, not returned
java;sorting;mergesort
You could dolist.clear(); merge(right, left, list);withprivate 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.