NOW Hiring

Quick links

Share

Mergesort with Java. This article describes how to implement Mergesort with Java.

1. Mergesort

1.1. Overview

The Mergesort algorithm can be used to sort a collection of objects. Mergesort is a so called divide and conquer algorithm. Divide and conquer algorithms divide the original data into smaller sets of data to solve the problem.

1.2. Mergesort

During the Mergesort process the objects of the collection are divided into two collections. To split a collection, Mergesort will take the middle of the collection and split the collection into its left and its right part.

The resulting collections are again recursively sorted via the Mergesort algorithm.

Once the sorting process of the two collections is finished, the result of the two collections is combined. To combine both collections Mergesort starts in each collection at the beginning. It picks the object which is smaller and inserts this object into the new collection. For this collection it now selects the next elements and selects the smaller element from both collections.

Once all elements from both collections have been inserted in the new collection, Mergesort has successfully sorted the collection.

To avoid the creation of too many collections, typically one new collection is created and the left and right side are treated as different collections.

1.3. Comparison with Quicksort

In comparison to Quicksort the divide part in Mergesort is simple, while the merging part is complex.

Quicksort can sort "inline" in an existing collection, e.g. it does not have to create a copy of the collection while Mergesort requires a copy.

2. Mergesort in Java

2.1. Implementation

Create a Java project called de.vogella.algorithms.sort.mergesort.

Create the following program.

package de.vogella.algorithms.sort.mergesort;

public class Mergesort {
        private int[] numbers;
        private int[] helper;

        private int number;

        public void sort(int[] values) {
                this.numbers = values;
                number = values.length;
                this.helper = new int[number];
                mergesort(0, number - 1);
        }

        private void mergesort(int low, int high) {
                // check if low is smaller then high, if not then the array is sorted
                if (low < high) {
                        // Get the index of the element which is in the middle
                        int middle = low + (high - low) / 2;
                        // Sort the left side of the array
                        mergesort(low, middle);
                        // Sort the right side of the array
                        mergesort(middle + 1, high);
                        // Combine them both
                        merge(low, middle, high);
                }
        }

        private void merge(int low, int middle, int high) {

                // Copy both parts into the helper array
                for (int i = low; i <= high; i++) {
                        helper[i] = numbers[i];
                }

                int i = low;
                int j = middle + 1;
                int k = low;
                // Copy the smallest values from either the left or the right side back
                // to the original array
                while (i <= middle && j <= high) {
                        if (helper[i] <= helper[j]) {
                                numbers[k] = helper[i];
                                i++;
                        } else {
                                numbers[k] = helper[j];
                                j++;
                        }
                        k++;
                }
                // Copy the rest of the left side of the array into the target array
                while (i <= middle) {
                        numbers[k] = helper[i];
                        k++;
                        i++;
                }

        }
}

2.2. Test

You can use the following JUnit test to validate your sort method. If you do not want to use JUnit you can convert the test methods into a normal Java main method.

package de.vogella.algorithms.sort.mergesort;

import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

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

import org.junit.Before;
import org.junit.Test;

public class MergesortTest {

        private int[] numbers;
        private final static int SIZE = 7;
        private final static int MAX = 20;

        @Before
        public void setUp() throws Exception {
                numbers = new int[SIZE];
                Random generator = new Random();
                for (int i = 0; i < numbers.length; i++) {
                        numbers[i] = generator.nextInt(MAX);
                }
        }

        @Test
        public void testMergeSort() {
                long startTime = System.currentTimeMillis();

                Mergesort sorter = new Mergesort();
                sorter.sort(numbers);

                long stopTime = System.currentTimeMillis();
                long elapsedTime = stopTime - startTime;
                System.out.println("Mergesort " + elapsedTime);

                for (int i = 0; i < numbers.length - 1; i++) {
                        if (numbers[i] > numbers[i + 1]) {
                                fail("Should not happen");
                        }
                }
                assertTrue(true);

        }

        @Test
        public void itWorksRepeatably() {
                for (int i = 0; i < 200; i++) {
                        numbers = new int[SIZE];
                        Random generator = new Random();
                        for (int a = 0; a < numbers.length; a++) {
                                numbers[a] = generator.nextInt(MAX);
                        }
                        Mergesort sorter = new Mergesort();
                        sorter.sort(numbers);
                        for (int j = 0; j < numbers.length - 1; j++) {
                                if (numbers[j] > numbers[j + 1]) {
                                        fail("Should not happen");
                                }
                        }
                        assertTrue(true);
                }
        }

        @Test
        public void testStandardSort() {
                long startTime = System.currentTimeMillis();
                Arrays.sort(numbers);
                long stopTime = System.currentTimeMillis();
                long elapsedTime = stopTime - startTime;
                System.out.println("Standard Java sort " + elapsedTime);

                for (int i = 0; i < numbers.length - 1; i++) {
                        if (numbers[i] > numbers[i + 1]) {
                                fail("Should not happen");
                        }
                }
                assertTrue(true);
        }

}

3. Complexity Analysis

The following describes the runtime complexity of mergesort.

Mergesort sorts in worst case in O(n log n) time. Due to the required copying of the collection Mergesort is in the average case slower then Quicksort.

4. About this website

5. Links and Literature

5.1. Source Code

Not listed yet.

5.3. vogella GmbH training and consulting support

TRAINING SERVICE & SUPPORT

The vogella company provides comprehensive training and education services from experts in the areas of Eclipse RCP, Android, Git, Java, Gradle and Spring. We offer both public and inhouse training. Whichever course you decide to take, you are guaranteed to experience what many before you refer to as “The best IT class I have ever attended”.

The vogella company offers expert consulting services, development support and coaching. Our customers range from Fortune 100 corporations to individual developers.

Copyright © 2012-2016 vogella GmbH. Free use of the software examples is granted under the terms of the EPL License. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.

See Licence.