Merge sort -.Java

public class MergeSort {

    public static void mergeSort(int[] a, int low, int high){

        int N = high - low;
        if(N<=1)
            return;
        int mid = low + N/2;
        mergeSort(a, low, mid);        mergeSort(a, mid, high);
        int temp[] = new int[N];
        int i = low;        int j = mid;
        for (int k = 0; k < N; k++) {

            if(i == mid)
                temp[k] = a[j++];
            else if(j == high)
                temp[k] = a[i++];
            else if (a[j] < a[i])
                temp[k] = a[j++];
            else                temp[k] = a[i++];        }

        for (int k = 0; k < N; k++) {
            a[low + k] = temp[k];        }

    }

    public static void main(String[] args) {
        int[] a = new int[] {2,6,3,7,1,9,4};        mergeSort(a, 0, a.length);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);        }
    }
}

O/p: 

1
2
3
4
6
7
9

http://www.geeksforgeeks.org/wp-content/uploads/Merge-Sort-Tutorial.png




public class MyMergeSort {

     

    private int[] array;

    private int[] tempMergArr;

    private int length;

    public static void main(String a[]){

         

        int[] inputArr = {45,23,11,89,77,98,4,28,65,43};

        MyMergeSort mms = new MyMergeSort();

        mms.sort(inputArr);

        for(int i:inputArr){

            System.out.print(i);

            System.out.print(" ");

        }

    }

     

    public void sort(int inputArr[]) {

        this.array = inputArr;

        this.length = inputArr.length;

        this.tempMergArr = new int[length];

        doMergeSort(0, length - 1);

    }

    private void doMergeSort(int lowerIndex, int higherIndex) {

         

        if (lowerIndex < higherIndex) {

            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;

            // Below step sorts the left side of the array

            doMergeSort(lowerIndex, middle);

            // Below step sorts the right side of the array

            doMergeSort(middle + 1, higherIndex);

            // Now merge both sides

            mergeParts(lowerIndex, middle, higherIndex);

        }

    }

    private void mergeParts(int lowerIndex, int middle, int higherIndex) {

        for (int i = lowerIndex; i <= higherIndex; i++) {

            tempMergArr[i] = array[i];

        }

        int i = lowerIndex;

        int j = middle + 1;

        int k = lowerIndex;

        while (i <= middle && j <= higherIndex) {

            if (tempMergArr[i] <= tempMergArr[j]) {

                array[k] = tempMergArr[i];

                i++;

            } else {

                array[k] = tempMergArr[j];

                j++;

            }

            k++;

        }

        while (i <= middle) {

            array[k] = tempMergArr[i];

            k++;

            i++;

        }

    }

}

- See more at: http://java2novice.com/java-sorting-algorithms/merge-sort/#sthash.U7Fvddai.dpuf

------------------------------------------------------------------------------------------------------------

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]+" ");
        }
    }
}

Source: http://javahungry.blogspot.com/2013/06/java-sorting-program-code-merge-sort.html

------------------------------------------------------------