Merge Sort : Java Sorting Program Code along with Example

Merge sort is a divide and conquer algorithm  that was invented by John von Neumann in 1945.

 Merge sort works as follows

*   Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

*    Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the  sorted list.

Read Also :    Quick Sort in Simple words with Example

 There are naturaly two types of merge sort
* Top down approach
* Bottom Up approach

When to Use

Here runtime mostly depends upon the pivotal element you choose .You can see  by running the below algorithm for

(Input)(Space)                           (Time taken)
10 elements           :           Merge sort took   0  milliseconds
100 elements         :           Merge sort took   0  milliseconds

1000 elements       :           Merge sort took   1  milliseconds 

10000 elements     :           Merge sort took   3  milliseconds
100000 elements   :           Merge sort took   97  milliseconds

Big O Notation

In simple words , Big O allows us to say something about how the size of inputs affect the runtime of a program .This technique can also be applied to other resources that an algorithm takes up (such as memory)
and we can analyze other bounds than the upper bound such as lower bound on time or space or expected time or space that an algorithm takes up .

Properties

* It is a  Stable algorithm i.e does not change the relative order of elements with equal keys
* It does not require random access to data

Best , Average,Worst Cases

*  Best Case        :    O(n log n) , or
                                O(n)  
* Average Case   :    O(n log n)
* Worst Case      :    O(n log n)

Read Also :     Insertion Sort
               
                                Bubble Sort                
    
                                Selection Sort 
              


Demo here :

Mergesort Code :

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;

public class MergeSort {
    
    
    public static int[] mergeSort(int [] list) {
        if (list.length <= 1) {
            return list;
        }
        
        // Split the array in half
        int[] first = new int[list.length / 2];
        int[] second = new int[list.length - first.length];
        System.arraycopy(list, 0, first, 0, first.length);
        System.arraycopy(list, first.length, second, 0, second.length);
        
        // Sort each half
        mergeSort(first);
        mergeSort(second);
        
        // Merge the halves together, overwriting the original array
        merge(first, second, list);
        return list;
    }
    
    private static void merge(int[] first, int[] second, int [] result) {
        // Merge both halves into the result array
        // Next element to consider in the first array
        int iFirst = 0;
        // Next element to consider in the second array
        int iSecond = 0;
        
        // Next open position in the result
        int j = 0;
        // As long as neither iFirst nor iSecond is past the end, move the
        // smaller element into the result.
        while (iFirst < first.length && iSecond < second.length) {
            if (first[iFirst] < second[iSecond]) {
                result[j] = first[iFirst];
                iFirst++;
                } else {
                result[j] = second[iSecond];
                iSecond++;
            }
            j++;
        }
        // copy what's left
        System.arraycopy(first, iFirst, result, j, first.length - iFirst);
        System.arraycopy(second, iSecond, result, j, second.length - iSecond);
    }
    
    
    
    
    
    public static void main(String args[]) throws Exception
    {
        String list="";
        int i=0,n=0;
        
        MergeSort s= new MergeSort();
        ArrayList<Integer> arrlist=new ArrayList<Integer>();
        System.out.println(" ");
        System.out.println(" ");
        System.out.println("Please enter the list of elements,one element per line");
        System.out.println(" write 'STOP' when list is completed ");
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        while(!(list=bf.readLine()).equalsIgnoreCase("stop")){
            int intelement=Integer.parseInt(list);
            arrlist.add(intelement);
            
        }
        
        int elementlist[]  = new int[arrlist.size()];
        Iterator<Integer> iter = arrlist.iterator();
        for (int j=0;iter.hasNext();j++) {
            elementlist[j] = iter.next();
        }
        
        elementlist=mergeSort(elementlist);
        System.out.println(" ");
        System.out.println(" ");
        System.out.println(" ");
        System.out.println("Values after Merge Sort : ");
        for (int j=0;j<elementlist.length;j++) {
            System.out.println(elementlist[j]+" ");
        }
    }
}