How to implement Merge Sort Algorithm in Java [Solved] - Example Tutorial

The merge sort algorithm is a divide and conquers algorithm. In the divide and conquer paradigm, a problem is broken into smaller problems where each small problem still retains all the properties of the larger problem -- except its size. To solve the original problem, each piece is solved individually; then the pieces are merged back together. For example, imagine you have to sort an array of 200 elements using the bubble sort algorithm. Since selection sort takes O(n^2) time, it would take about 40,000-time units to sort the array. Now imagine splitting the array into ten equal pieces and sorting each piece individually still using selection sort. Now it would take 400-time units to sort each piece; for a grand total of 10*400 = 4000.

Once each piece is sorted, merging them back together would take about 200-time units; for a grand total of 200+4000 = 4,200. Clearly, 4,200 is an impressive improvement over 40,000.

Now think bigger. Imagine splitting the original array into groups of two and then sorting them. In the end, it would take about 1,000-time units to sort the array.

That's how merge sort works. It makes sorting a big array easy and hence it's suitable for large integer and string arrays. Time Complexity of the mergesort algorithm is the same in the best, average, and worst-case and it's equal to O(n*log(n))

Btw, if you are new to Algorithms and Data Structure and not familiar with essential sorting and searching algorithms like quicksort, binary search, level order search, etc then I suggest you go through a good, comprehensive online course like Data Structures and Algorithms: Deep Dive Using Java to learn the basics first.

Sorting Array in Java using Merge Sort Algorithm - Example

You have given an unordered list of integers (or any other objects e.g. String), You have to rearrange the integers or objects in their natural order.

Sample Input: {80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 5}
Sample Output: {0, 10, 20, 30, 40, 50, 50, 60, 70, 80, 90}

import java.util.Arrays;

/*
 * Java Program to sort an integer array using merge sort algorithm.
 */

public class Main {

  public static void main(String[] args) {

    System.out.println("mergesort");
    int[] input = { 87, 57, 370, 110, 90, 610, 02, 710, 140, 203, 150 };

    System.out.println("array before sorting");
    System.out.println(Arrays.toString(input));

    // sorting array using MergeSort algorithm
    mergesort(input);

    System.out.println("array after sorting using mergesort algorithm");
    System.out.println(Arrays.toString(input));

  }

  /**
   * Java function to sort given array using merge sort algorithm
   * 
   * @param input
   */
  public static void mergesort(int[] input) {
    mergesort(input, 0, input.length - 1);
  }

  /**
   * A Java method to implement MergeSort algorithm using recursion
   * 
   * @param input
   *          , integer array to be sorted
   * @param start
   *          index of first element in array
   * @param end
   *          index of last element in array
   */
  private static void mergesort(int[] input, int start, int end) {

    // break problem into smaller structurally identical problems
    int mid = (start + end) / 2;
    if (start < end) {
      mergesort(input, start, mid);
      mergesort(input, mid + 1, end);
    }

    // merge solved pieces to get solution to original problem
    int i = 0, first = start, last = mid + 1;
    int[] tmp = new int[end - start + 1];

    while (first <= mid && last <= end) {
      tmp[i++] = input[first] < input[last] ? input[first++] : input[last++];
    }
    while (first <= mid) {
      tmp[i++] = input[first++];
    }
    while (last <= end) {
      tmp[i++] = input[last++];
    }
    i = 0;
    while (start <= end) {
      input[start++] = tmp[i++];
    }
  }
}

Output
mergesort
array before sorting
[87, 57, 370, 110, 90, 610, 2, 710, 140, 203, 150]
array after sorting using mergesort algorithm
[2, 57, 87, 90, 110, 140, 150, 203, 370, 610, 710]

You can see that the array is now sorted. The algorithm we have used is a recursive implementation of merge sort and it's also a stable sorting algorithm I mean it maintains the original order of elements in case of a tie.

Anyway, if you haven't got it yet that how the merge sort algorithm works, you can also check out the Algorithms and Data Structures - Part 1 and 2  course on Pluralsight which explains key sorting and searching algorithms in a very nice way. It also covers essential data structures like a linked list, array, hash table, binary tree, etc.

That's all about how to implement the merge sort algorithm in Java. Along with Quicksort it's an important sorting algorithm and used in many real-world, general-purpose libraries. In fact, Java's Collections.sort() and Arrays.sort() method also used a variant of merge sort for soring objects.

If you are preparing for a programming job interview then you must know how to implement it by hand and find out time and space complexity. You should also be able to explain the difference between merge sort and quicksort if asked.

The key thing to remember here is that even though both merge sort and quick sort have an average case time complexity of O(NlogN), quicksort is better than merge sort because the constant associated with quicksort is lesser than merge sort.

In reality, O(NlogN) is K*O(nLogN), Big O notation ignores that constant because it gets irrelevant when input size increases exponentially but for algorithms with the same time complexity, this constant could be a differentiating factor, just like it is in the case of quicksort and mergesort.

You should also remember that it's a recursive algorithm and can be easily implemented using recursion.

If you like this article and would like to try out a couple of more challenging programming exercises, then take a look at the following programming questions from various Interviews :

• How to check if LinkedList contains any cycle in Java? (solution)
• How to search an element in an array in Java? (solution)
• How to sort an array using the bubble sort algorithm? (algorithm)
• How to calculate Sum of Digits of a number in Java? (Solution)
• Write a program to find the first non-repeated characters from String in Java? (program)
• How to declare and initialize a two-dimensional array in Java? (solution)
• Write a method to count occurrences of a character in String? (Solution)
• How to check if a number is an Armstrong number or not? (solution)
• Write a Program to remove duplicates from an array without using Collection API? (program)
• How to reverse String in Java without using API methods? (Solution)
• Write a method to remove duplicates from ArrayList in Java? (Solution)
• How to check if a number is binary in Java? (answer)
• Write a program to check if a number is Prime or not? (solution)
• How to find the largest prime factor of a number in Java? (solution)
• How to calculate a factorial using recursion in Java? (algorithm)
• Write a program to check if a number is a Palindrome or not? (program)
• Write a program to check if the Array contains a duplicate number or not? (Solution)
• How to find the Fibonacci sequence up to a given number? (solution)
• Write a program to find a missing number in a sorted array? (algorithm)
• How to find the top two maximum on integer array in Java? (solution)
• Write a method to check if two String are Anagram of each other? (method)
• How to find the largest and smallest number in an array? (solution)
• Write a function to find the middle element of the linked list in one pass? (solution)
• How to solve the Producer-Consumer Problem in Java. (solution)
• Write a Program to Check if a number is Power of Two or not? (program)

Thanks for reading this article so far. If you like this Merge sort example in Java then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.  Btw, what is your favorite sorting algorithm? Bubble Sort, Quick Sort, or Merge Sort?


P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers. This list contains free data structure courses from sites like Udemy, Coursera, and Pluralsight.