Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Parallel Merge Sort in Java

farenda 2017-03-30 0

Divide and Conquer algorithms are great subject for parallelism. Here we present Parallel Merge Sort implemented using Java ForkJoin Framework.

Parallel sort steps

Parallel Merge Sort consists of the same steps as other tasks executed in ForkJoin Pool, namely:

  1. If the task is small enough – do it directly.
    In case of Merge Sort we can decide that when a subarray to sort is smaller than some value (we name it SORT_THRESHOLD), then we’ll resort to the Insertion Sort, which will sort it in-place.
  2. Else do Merge Sort of both parts as separate tasks, executed in a ForkJoin Pool. This will allow us to sort parts of an array independently and then just merge them.

MergSort as RecursiveAction

The implementation consists of a few key points we need to do:

  • extend RecursiveAction to allow execution in ForkJoin Pool
  • decide when to sort directly
  • execute parallel tasks for subarrays
  • merge everything at the end.

Therefore the heart of the Parallel Merge Sort with Fork Join Framework looks like this:

import java.util.concurrent.RecursiveAction;

public class ParallelMergeSort extends RecursiveAction {

    // Decides when to fork or compute directly:
    private static final int SORT_THRESHOLD = 128;

    // Defines subarray to sort:
    public ParallelMergeSort(int[] values, int from, int to)

    @Override
    protected void compute() {
        if (from < to) {
            int size = to - from;
            if (size < SORT_THRESHOLD) {
                // Sort in-place using Insertion Sort:
                insertionSort();
            } else {
                int mid = from + Math.floorDiv(size, 2);
                // Do MergeSort in parallel on subarrays.
                // This will submit the tasks to the current
                // ForkJoin Pool:
                invokeAll(
                        new ParallelMergeSort(values, from, mid),
                        new ParallelMergeSort(values, mid + 1, to));
                // Merge sorted subarrays:
                merge(mid);
            }
        }
    }
    // ...
}

Complete Parallel Merge Sorter

This is complete implementation of Parallel Merge Sort using Fork-Join Framework to do parallel execution:

package com.farenda.tutorials.algorithms.sorting;

import java.util.Arrays;
import java.util.concurrent.RecursiveAction;

public class ParallelMergeSort extends RecursiveAction {

    // Decides when to fork or compute directly:
    private static final int SORT_THRESHOLD = 128;

    private final int[] values;
    private final int from;
    private final int to;

    public ParallelMergeSort(int[] values) {
        this(values, 0, values.length-1);
    }

    public ParallelMergeSort(int[] values, int from, int to) {
        this.values = values;
        this.from = from;
        this.to = to;
    }

    public void sort() {
        compute();
    }

    @Override
    protected void compute() {
        if (from < to) {
            int size = to - from;
            if (size < SORT_THRESHOLD) {
                insertionSort();
            } else {
                int mid = from + Math.floorDiv(size, 2);
                invokeAll(
                        new ParallelMergeSort(values, from, mid),
                        new ParallelMergeSort(values, mid + 1, to));
                merge(mid);
            }
        }
    }

    private void insertionSort() {
        for (int i = from+1; i <= to; ++i) {
            int current = values[i];
            int j = i-1;
            while (from <= j && current < values[j]) {
                values[j+1] = values[j--];
            }
            values[j+1] = current;
        }
    }

    private void merge(int mid) {
        int[] left = Arrays.copyOfRange(values, from, mid+1);
        int[] right = Arrays.copyOfRange(values, mid+1, to+1);
        int f = from;

        int li = 0, ri = 0;
        while (li < left.length && ri < right.length) {
            if (left[li] <= right[ri]) {
                values[f++] = left[li++];
            } else {
                values[f++] = right[ri++];
            }
        }

        while (li < left.length) {
            values[f++] = left[li++];
        }

        while (ri < right.length) {
            values[f++] = right[ri++];
        }
    }
}

Test and performance comparison

As usually we need to check somehow that it works. :-) But for brevity we’ll show only JUnit test for substantial amount of data (100 millions) and we’ll do that for both Merge Sort and Parallel Merge Sort:

package com.farenda.tutorials.algorithms.sorting;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

import static org.junit.Assert.assertArrayEquals;

public class ParallelMergeSortTest {

    //... other tests cut for brevity

    @Test
    public void performanceTest() {
        int[] serial = new Random().ints(100_000_000).toArray();
        int[] parallel = Arrays.copyOf(serial, serial.length);

        MergeSort mergeSort = new MergeSort();
        long start = System.currentTimeMillis();
        mergeSort.sort(serial);
        System.out.println("Merge Sort done in: "
                + (System.currentTimeMillis()-start));

        ParallelMergeSort sorter = new ParallelMergeSort(parallel);
        start = System.currentTimeMillis();
        sorter.sort();
        System.out.println("Parallel Merge Sort done in: "
                + (System.currentTimeMillis()-start));

        assertArrayEquals(parallel, serial);
    }
}

I run that a few times on my laptop with 2 Cores and the results were around this:

Merge Sort done in: 31077
Parallel Merge Sort done in: 20020

Clearly Parallel Merge Sort is much faster for arrays of 100M of elements. The speedup is not 2x, because there are overheads for scheduling tasks in pool, but still the difference is substantial.

Both sorting algorithms use Insertion Sort when subarray to sort is below defined threshold. I found value 128 to give pretty good results – maybe there is a better value around, but it gave better results than values 64, 256, 512, 768, 1024, etc.

References:

  • See details of Insertion Sort
  • See detailed explanation of Merge Sort
  • ForkJoin explained
  • Check out other algorithms in Algorithms Tutorial
Share with the World!
Categories Algorithms Tags algorithms, java, java-concurrency
Previous: “Turning the database inside out with Apache Samza” by Martin Kleppmann
Next: MongoDB import/export data

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2022

sponsored