tl  tr
  Home | Tutorials | Articles | Videos | Products | Tools | Search
Interviews | Open Source | Tag Cloud | Follow Us | Bookmark | Contact   
 Data Structures > Sort > Merge Sort

Merge Sort 

The following example shows merge sort implementation.

  • Best case time complexity of merge sort is O(n log n)
  • Worst case time complexity of merge sort is O(n log n)
  • Average case time complexity of merge sort is O(n log n)

File Name  :  
com/bethecoder/tutorials/ds/sort/MergeSort.java 
Author  :  Sudhakar KV
Email  :  [email protected]
   
package com.bethecoder.tutorials.ds.sort;

import java.util.Arrays;

public class MergeSort {

  /**
   @param args
   */
  public static void main(String[] args) {

    int[] list = 11223376651839402711261219278619 };
    System.out.println("Before sort : " + Arrays.toString(list));
    double timeTaken = mergeSortTimeTaken(list);
    System.out.println("After sort : " + Arrays.toString(list));
    System.out.println("Time taken for MergeSort : " + timeTaken + " milliseconds.");
  }

  /**
   @param list
   */
  public static int[] mergeSort(int[] list) {
    /**
     * Boundary condition for recursive method.
     * An array with ZERO or ONE element is
     * already sorted.
     */
    if (list == null || list.length <= 1) {
      return list;
    }
    
    /**
     * 1. Divide the list into two sub list.
     * 2. Sort each subset.
     * 3. Merge the two subsets.
     */
    int[] leftSubList = new int[list.length/2];
      System.arraycopy(list, 0, leftSubList, 0, leftSubList.length);

      int[] rightSubList = new int[list.length-leftSubList.length];
      System.arraycopy(list, leftSubList.length, rightSubList, 0, rightSubList.length);
      
      leftSubList = mergeSort(leftSubList);
      rightSubList = mergeSort(rightSubList);

      merge(leftSubList, rightSubList, list);
      return list;
  }
  
  private static void merge(int[] leftSubList, int[] rightSubList, int[] list) {
    int index = 0, leftIndex = 0, rightIndex = 0;
    
    while (index < list.length && 
        (leftIndex < leftSubList.length || rightIndex < rightSubList.length)) {
      
      if (leftIndex < leftSubList.length && rightIndex < rightSubList.length) {
        if (leftSubList[leftIndex< rightSubList[rightIndex]) {
          list[index= leftSubList[leftIndex]; leftIndex ++;
        else {
          list[index= rightSubList[rightIndex]; rightIndex ++;
        }
      else if (leftIndex < leftSubList.length) {
        list[index= leftSubList[leftIndex]; leftIndex ++;
      else if (rightIndex < rightSubList.length) {
        list[index= rightSubList[rightIndex]; rightIndex ++;
      }
      
      index ++;
    }
  }

  /**
   * Sorts and returns the time taken in milliseconds.
   
   @param list
   @return
   */
  public static double mergeSortTimeTaken(int[] list) {
    long startTime = System.nanoTime();
    mergeSort(list);
    long timeTaken = System.nanoTime() - startTime;
    return timeTaken * Math.pow(10, -6);
  }
}
   

It gives the following output,
Before sort : [112, 23, 376, 6, 5, 1, 8, 3, 9, 4, 0, 2, 7, 11, 26, 12, 19, 27, 86, 19]
After sort : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 19, 19, 23, 26, 27, 86, 112, 376]
Time taken for MergeSort : 0.026261 milliseconds.



 
  


  
bl  br