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 = { 112, 23, 376, 6, 5, 1, 8, 3, 9, 4, 0, 2, 7, 11, 26, 12, 19, 27, 86, 19 };     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);   } }

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.