1
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That helps quite a bit. I think I'm hovering over a solution that will perform the sort in-place, instead of adding to new lists all the time. \$\endgroup\$ – Sotirios Delimanolis Oct 22 '13 at 19:19
  • 1
    \$\begingroup\$ In-place mergesort is complicated. Better use a different sorting algorithm, then. \$\endgroup\$ – 200_success Oct 22 '13 at 19:23
  • \$\begingroup\$ Thank you for the reference. Is there anywhere else I can improve? \$\endgroup\$ – Sotirios Delimanolis Oct 22 '13 at 19:25
  • \$\begingroup\$ if (length <= 1) return;. By returning early, you don't need else, which just adds unnecessary indentation. \$\endgroup\$ – 200_success Oct 22 '13 at 23:39
  • \$\begingroup\$ You can save two lines by saying left.get(leftIndex++) and right.get(rightIndex++) during "add remaining". \$\endgroup\$ – 200_success Oct 22 '13 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.