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 algorithm description
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.
4. Links and Literature
Nothing listed.
4.1. vogella Java example code
If you need more assistance we offer Online Training and Onsite training as well as consulting