Merge Sort in Java - Algorithm Example and 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 its 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 an 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 using Merge Sort Algorithm:

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 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 linked list, array, hash table, binary tree etc. 

Mergesort in Java - Algorithm Example and tutorial


Btw, you would need a Pluralsight membership to access this course, which cost around $29 per month or $299 per year but also provides you access to all of their 5000+ online courses on latest technologies.

I have Pluralsight membership and I highly recommend to any programmer who wants to keep himself up-to-date and upgrade his skills. Btw, even if you don't have the membership, you can still access this course for free by taking advantage of their 10-day free pass which allows free access for 200 minutes.


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 library. 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 has 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 ignore that constant because it gets irrelevant when input size increases exponentially but for algorithms with 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.


Further Reading
Algorithms and Data Structures - Part 1 and 2 
Data Structure and Algorithms Analysis - Job Interview
Data Structures and Algorithms: Deep Dive Using Java
From 0 to 1: Data Structures & Algorithms in Java
Cracking the Coding Interview - 189 Questions and Solutions


If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at following programming questions from various Interviews :
  • How to check if LinkedList contains any cycle in Java? (solution)
  • How to search element in an array in Java? (solution)
  • How to sort an array using bubble sort algorithm? (algorithm)
  • How to calculate Sum of Digits of a number in Java? (Solution)
  • Write a program to find 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 Armstrong number or not? (solution)
  • Write a Program 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 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 middle element of 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 with your friends and colleagues. If you have any questions or feedback then please drop a note.


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.

No comments:

Post a Comment