0

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) {
        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);
    }
}
  • As per [guide to Code Review for Stack Overflow users](https://codereview.meta.stackexchange.com/questions/5777/a-guide-to-code-review-for-stack-overflow-users), I think this question is better suited for https://codereview.stackexchange.com/. – lexicore Apr 26 '18 at 20:16
  • @lexicore hmm didnt even know that existed – Jeffrey Phillips Freeman Apr 26 '18 at 20:17
  • 1
    Much better that previous "beat my solution and I'll accept your answer". – lexicore Apr 26 '18 at 20:18
  • @lexicore I really just figured my solution would be helpful to people in the future so wanted to share. I couldnt find an in-place mergesort on java anywhere so thought it would be helpful to post somewhere. – Jeffrey Phillips Freeman Apr 26 '18 at 20:19
  • `Collections.sort` is actually a mergesort ([Timsort](https://en.wikipedia.org/wiki/Timsort)). – lexicore Apr 26 '18 at 20:23
  • @lexicore ohh thanks, didnt know that. I need to find the source code for it, it could (and likely is) a better example than my own. – Jeffrey Phillips Freeman Apr 26 '18 at 20:25
  • See `java.util.TimSort`. – lexicore Apr 26 '18 at 20:26
  • @lexicore The one you suggest as a duplicate is not in place, and it uses arrays. Which makes it a significantly different question. – Jeffrey Phillips Freeman Apr 26 '18 at 20:27
  • @lexicore aside from that question being a mergesort it isnt even close to the same. It isnt even in place. – Jeffrey Phillips Freeman Apr 26 '18 at 20:28
  • Also see `java.util.Arrays.parallelSort(T[])`. – lexicore Apr 26 '18 at 20:34
  • Is the example code in the question really in place? The usual implementation of in place merge sort sorts the right half and the first left quarter of the list. Then those are merged starting at the second quarter, swapping elements instead of moving elements, leaving the first quarter unsorted and the right three quarters sorted. Then this is repeated, using 1st and 2nd eight of the list, and so on, until the left sub-list is only 2 elements, at which point an insertion sort is used. For k threads, each sub-list could be split into k parts to sort in parallel. – rcgldr Apr 27 '18 at 22:14

0 Answers0