Merge sort, Multiple languages

MergeSort.hs

mergeSort :: (Ord a) => [a] -> [a]
mergeSort x
    | len <= 1 = x
    | otherwise = combine (mergeSort upper) (mergeSort lower)
    where len = length x
          middle = quot len 2
          upper = take middle x
          lower = drop middle x
          combine x [] = x
          combine [] x = x
          combine xAll@(x:xl) yAll@(y:yl)
                | x < y = x:combine xl yAll
                | otherwise = y:combine xAll yl

MergeSort.java

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 = new ArrayList<>(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();

            List<N> sorted = new ArrayList<>();
            while(!left.isEmpty() || !right.isEmpty()) {
                if(left.isEmpty())
                    sorted.add(right.remove(0));
                else if(right.isEmpty())
                    sorted.add(left.remove(0));
                else {
                    if( left.get(0).compareTo(right.get(0)) < 0 )
                        sorted.add(left.remove(0));
                    else
                        sorted.add(right.remove(0));
                }
            }

            return sorted;
        }
    }

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

MergeSort.js

function mergeSort()
{
  var unsortedValues = Array.prototype.slice.call(arguments);
  return mergeSortArray(unsortedValues);
}

function mergeSortArray(unsortedValues)
{
  if(unsortedValues.length <= 1)
    return unsortedValues;
    
  var middleIndex = Math.floor(unsortedValues.length/2);
  
  var bottomValues = unsortedValues.slice(0, middleIndex);
  var topValues = unsortedValues.slice(middleIndex, unsortedValues.length);
  
  //if the top or bottom halves have more than one element in them, recursively
  //sort them first
  if(bottomValues.length > 1)
    bottomValues = mergeSortArray(bottomValues);
  if(topValues.length > 1)
    topValues = mergeSortArray(topValues);
    
  //now is where we merge the two arrays. We have two sorter arrays we want to
  //merge into one larger sorted array.
  var bottomIndex = 0;
  var topIndex = 0;
  var sortedIndex = 0;
  var sortedValues = new Array(unsortedValues.length);
  
  while( sortedIndex < sortedValues.length )
  {
    //check if there is just one half of the array left
    if(bottomIndex >= bottomValues.length)
    {
      while(topIndex < topValues.length)
      {
        sortedValues[sortedIndex] = topValues[topIndex];
        topIndex++;
        sortedIndex++;
      }
    }
    else if(topIndex >= topValues.length)
    {
      while(bottomIndex < bottomValues.length)
      {
        sortedValues[sortedIndex] = bottomValues[bottomIndex];
        bottomIndex++;
        sortedIndex++;
      }
    }
    //since both arrays are still in play lets do our comparison and sort
    else if(bottomValues[bottomIndex] < topValues[topIndex])
    {
      sortedValues[sortedIndex] = bottomValues[bottomIndex];
      sortedIndex++;
      bottomIndex++;
    }
    else
    {
      sortedValues[sortedIndex] = topValues[topIndex];
      sortedIndex++;
      topIndex++;
    }
  }
  
  return sortedValues;
}

MergeSortInPlace.java

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

public class MergeSortInPlace<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;
            MergeSortInPlace<N> leftTask = new MergeSortInPlace<N>(this.elements.subList(0, pivot));
            MergeSortInPlace<N> rightTask = new MergeSortInPlace<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(rightIndex >= right.size()) {
                    if(right.get(0).compareTo(left.get(left.size() - 1)) < 0 )
                        merge(left, right);
                    else
                        return;
                }
                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(5,9,8,7,6,1,2,3,4))));
        System.out.println("result: " + result);
    }
}

MergeSortReuse.java

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

public class MergeSortReuse<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 new LinkedList<>(this.elements);
        else {
            final int pivot = this.elements.size() / 2;
            MergeSortReuse<N> leftTask = new MergeSortReuse<N>(this.elements.subList(0, pivot));
            MergeSortReuse<N> rightTask = new MergeSortReuse<N>(this.elements.subList(pivot, this.elements.size()));

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

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

            return merge(left, right);
        }
    }

    private List<N> merge(List<N> left, List<N> right) {
        ListIterator<N> leftIter = left.listIterator();
        ListIterator<N> rightIter = right.listIterator();
        while(leftIter.hasNext() || rightIter.hasNext()) {
            if(!leftIter.hasNext()) {
                leftIter.add(rightIter.next());
                rightIter.remove();
            }
            else if(!rightIter.hasNext())
                return left;
            else {
                N rightElement = rightIter.next();
                if( leftIter.next().compareTo(rightElement) < 0 )
                    rightIter.previous();
                else {
                    leftIter.previous();
                    leftIter.add(rightElement);
                }
            }
        }

        return left;
    }

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