Support free tutorials









vogella training Training Books



Mergesort in Java - Tutorial

Lars Vogel

Version 2.1

15.11.2012

Mergesort with Java

This article describes how to implement Mergesort with Java.


Table of Contents

1. Mergesort
1.1. Overview
1.2. Mergesort
1.3. Comparison with Quicksort
2. Mergesort in Java
2.1. Implementation
2.2. Test
3. Complexity Analysis
4. Support this website
4.1. Thank you
4.2. Questions and Discussion
5. Links and Literature
5.1. Source Code
5.2. General

1. Mergesort

1.1. Overview

The Mergesort algorithm can be used to sort a collection of objects. Mergesort is 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 object in 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 start at each collection at the beginning. It pick 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 collection.

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 http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html Quicksort the divide part is simple in Mergesort while the merging take is complex.

Quicksort can sort "inline" of 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 http://www.vogella.com/tutorials/ComplexityAnalysis/article.html 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 http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html Quicksort.

4. Support this website

This tutorial is Open Content under the CC BY-NC-SA 3.0 DE license. Source code in this tutorial is distributed under the Eclipse Public License. See the vogella License page for details on the terms of reuse.

Writing and updating these tutorials is a lot of work. If this free community service was helpful, you can support the cause by giving a tip as well as reporting typos and factual errors.

4.1. Thank you

Please consider a contribution if this article helped you. It will help to maintain our content and our Open Source activities.

4.2. Questions and Discussion

If you find errors in this tutorial, please notify me (see the top of the page). Please note that due to the high volume of feedback I receive, I cannot answer questions to your implementation. Ensure you have read the vogella FAQ as I don't respond to questions already answered there.

5. Links and Literature

5.1. Source Code

Source Code of Examples

5.2. General

Not listed yet