Multi-threaded in-place Mergesort on Java

Question

What is an efficient way to implement the Mergesort algorithm in Java such that it meets the following criteria:

• Must be multi-threaded.
• Must retain the Mergesort time complexities.
• Must be in-place implementation, no copying arrays.
• Must use Java Collection classes, not an array.
• Must work on any Java Comparable.

My solution involves using an ArrayList and fork-join to create the in-place Mergesort. I've tested this on multiple inputs and they all work.

I'm curious if anyone can find a way I can improve my code. Either a more efficient solution or perhaps an edge case I didn't address.

import java.util.*;
import java.util.concurrent.*;

public class MergeSort<N extends Comparable<N>> extends RecursiveTask<List<N>> {
    private List<N> elements;

    public MergeSort(List<N> elements) {
        this.elements = elements;
    }

    @Override
    protected List<N> compute() {
        if(this.elements.size() <= 1)
            return this.elements;
        else {
            final int pivot = this.elements.size() / 2;
            MergeSort<N> leftTask = new MergeSort<N>(this.elements.subList(0, pivot));
            MergeSort<N> rightTask = new MergeSort<N>(this.elements.subList(pivot, this.elements.size()));

            leftTask.fork();
            rightTask.fork();

            List<N> left = leftTask.join();
            List<N> right = rightTask.join();

            merge(left, right);
            return this.elements;
        }
    }

    private void merge(List<N> left, List<N> right) {
        int leftIndex = 0;
        int rightIndex = 0;
        while(leftIndex < left.size()) {
            if(rightIndex == 0) {
                if( left.get(leftIndex).compareTo(right.get(rightIndex)) > 0 ) {
                    swap(left, leftIndex++, right, rightIndex++);
                } else {
                    leftIndex++;
                }
            } else {
                if( right.get(0).compareTo(right.get(rightIndex)) < 0 ) {
                    swap(left, leftIndex++, right, 0);
                } else {
                    swap(left, leftIndex++, right, rightIndex++);
                }
            }
        }

        if(rightIndex < right.size() && rightIndex != 0)
            merge(right.subList(0, rightIndex), right.subList(rightIndex, right.size()));
    }

    private void swap(List<N> left, int leftIndex, List<N> right, int rightIndex) {
        //N leftElement = left.get(leftIndex);
        left.set(leftIndex, right.set(rightIndex, left.get(leftIndex)));
    }

    public static void main(String[] args) {
        ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
        List<Integer> result = forkJoinPool.invoke(new MergeSort<Integer>(new ArrayList<>(Arrays.asList(1,3,5,7,2,4,6))));
        System.out.println("result: " + result);
    }
}

Update: The code will fail on the edge case where the following input integers are used:

{5,9,8,7,6,1,2,3,4}

This occurs because the recursive call to merge only works successfully when the left and right lists are of equal length or differ by only one in length. This call however will result in the comparison of two lists that breaks that expectation. I have yet to find a solution which handles all edge cases properly.

Answer 1

Quick-Glance nitpicks

• elements can (and should) be final. This reinforces the point that you're not changing that reference.
• Always place braces around blocks. That's especially true for single-line if-blocks like the element size guard. Somewhat interestingly inside merge you placed the braces in all if-blocks except the last.
• You're inconsistent in the spacing for conditionals. In merge the inner if-statement's conditionals are surrounded by spaces, everywhere else, they are not. I personally prefer putting a space before the opening parenthesis of any condition, if only to distinguish it from a method invocation.

Density of semantics

The swap calls in merge are rather heavy in what they do. There's a lot going on at once, relying on a conscious and full understanding of unary operators and how the method works.

If I were you, I'd consider extracting the incrementing of the indices to separate statements. That can also make the reasoning somewhat easier to understand, seeing that leftIndex++ is in every branch of the tree:

    while (leftIndex < left.size()) {
        if (rightIndex == 0) {
            if (left.get(leftIndex).compareTo(right.get(rightIndex)) > 0) {
                swap(left, leftIndex, right, rightIndex);
                rightIndex++;
            }
        } else if (right.get(0).compareTo(right.get(rightIndex)) > 0) {
            swap(left, leftIndex, right, 0);
        } else {
            swap(left, leftIndex, right, rightIndex);
            rightIndex++;
        }
        leftIndex++;
    }

At this point it should also be clear that the first if-statements can be collapsed into a single statement. JS1 mentions that the in-place merge you are doing does not work for all cases. Unfortunately I can't tell you quite exactly why, but making the code easier to grasp should help troubleshooting and fixing this :)

Optional List features

You're making use of the set operation on Lists. It's important to be aware that set is an optional operation. Not all implementations of List provide an implementation and may throw UnsupportedOperationExcpetion instead. Then again all the other features you could use to replace this are also optional (what with modification of Lists being optional)...