5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You need to rethink your merge() function, because it doesn't work properly even on cases where the left and right sides are of equal length. The problem is that you swap elements from the left side to the right side, but other than right[0], you don't revisit those elements and put them in the correct position. For example, once you swap some left element into right[1], you will never move that element again. As far as I know, there is no simple in-place merge algorithm that can be done the way you are trying to do it. \$\endgroup\$ – JS1 Apr 26 '18 at 22:41
  • 2
    \$\begingroup\$ You may want to look at this which explains how to do a proper in-place mergesort. \$\endgroup\$ – JS1 Apr 26 '18 at 22:49
  • \$\begingroup\$ @JS1 Yea i figured that much out myself. I think i can do it with a third index as a pointer. \$\endgroup\$ – Jeffrey Phillips Freeman Apr 26 '18 at 23:42
  • \$\begingroup\$ @JS1 Also thanks for the link. I did see that. It is fairly similar to my approach though im trying a slightly different approach. Not sure if it will be workable. \$\endgroup\$ – Jeffrey Phillips Freeman Apr 27 '18 at 0:13
2
\$\begingroup\$

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)...

\$\endgroup\$

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.