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 than 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++;
}
// Since we are sorting in-place any leftover elements from the right side
// are already at the right position.
}
}
```

### 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 than Quicksort.

## 5. Links and Literature

### 5.2. General

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. |

## Appendix A: Copyright and License

Copyright © 2012-2017 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.