Java Programming Tutorials

Java programming tutorials with many code examples!

Merge Sort in Java

In this post we’ll implement Merge Sort in Java. It’s fast, divide and conquer, sorting algorithm that can also be parallelized.

How Merge Sort works

The algorithm belongs to the group of Divide and Conquer family of algorithms. This basically means that it divides the sorting problem into smaller parts to solve. The core of Merge Sort goes as follows:

  1. When the array consists of only one element do nothing, because it is already sorted.
  2. Find the middle point of array (or mid points when you want to split into more parts).
  3. Recursively Merge Sort part of array from the start to the middle point.
  4. Recursively Merge Sort part of array above the middle point.
  5. Merge (join) both sorted parts.

The above algorithm can be simply expressed in Java code:

void mergeSort(int[] numbers, int from, int to) {
    if (from < to) {
        int mid = Math.floorDiv(from+to, 2);
        mergeSort(numbers, from, mid);
        mergeSort(numbers, mid+1, to);
        merge(numbers, from, mid, to);
    }
}

Merge Sort properties

The notable properties of Merge Sort are:

  • Merge Sort is stable sorting (preserves order of already sorted elements)
  • best/average/worst case performance is O(n log n)
  • memory complexity is O(n) (requires additional memory for n elements)
  • can be parallelized, because parts of array are sorted independently

Merge Sort implementation

The implementation is more complex than Selection Sort and Insertion Sort, but if you think about both Divide and Conquer parts then it won’t be hard to go through:

package com.farenda.tutorials.algorithms.sorting;

import java.util.Arrays;

public class MergeSort {

    public void sort(int[] numbers) {
        mergeSort(numbers, 0, numbers.length-1);
    }

    void mergeSort(int[] numbers, int from, int to) {
        if (from < to) {
            int mid = Math.floorDiv(from+to, 2);
            mergeSort(numbers, from, mid);
            mergeSort(numbers, mid+1, to);
            merge(numbers, from, mid, to);
        }
    }

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

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

        while (li < left.length) {
            numbers[from++] = left[li++];
        }

        while (ri < right.length) {
            numbers[from++] = right[ri++];
        }
    }
}

Unit tests

Here are some JUnit tests to verify the implementation:

package com.farenda.tutorials.algorithms.sorting;

import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

public class MergeSortTest {

    private MergeSort sorter = new MergeSort();

    @Test
    public void shouldDoNothingWithEmptyArray() {
        int[] values = {};

        sorter.sort(values);

        assertEquals(values.length, 0);
    }

    @Test
    public void shouldDoNothingWithOneElementArray() {
        int[] values = {42};

        sorter.sort(values);

        assertArrayEquals(new int[] {42}, values);
    }

    @Test
    public void shouldSortValues() {
        int[] values = new int[] { 9, -3, 5, 0, 1};
        int[] expectedOrder = new int[] { -3, 0, 1, 5, 9};

        sorter.sort(values);
        assertArrayEquals(expectedOrder, values);
    }
}

References:

Share with the World!