Sunday, 4 March 2018

Mergesort in Java - Algorithm Example

The Merge sort algorithm is a divide and conquers algorithm. In the divide and conquer paradigm, a problem is broken into small 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 selection 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 mergesort algorithm is same in best, average and worst case and it's equal to O(n*log(n))

Problem Statement:


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 array is now sorted. The algorithm we have used is a recursive implemention of merge sort and it's also an stable sorting algorithm i.e. it maintains the original order of elements in case of tie.

Anyway, if you haven't got it yet that how merge sort algorithm works, here is a nice diagaram to understand it better. A picture is said to be equal to 1000 words and that's true by looking at this diagram:

Oracle Java Tutorials and Materials, Oracle Java Guides, Oracle Java Learning

That's all about how to implement mergesort 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 varient of merge sort for soring objects.

If you are preparing for 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 explain the difference between merge sort and quicksort if asked. You should also remember that it's a recursive algorithm and can be easily implemented using recursion.

Related Posts