Sorting: Merge Sort

Sorting is a combination of algorithms or instructions that you give in Java for the program to organize an array of numbers either from smallest to biggest or from biggest to smallest, this helps for your computer to more easily and quickly run a program which has to find a specific number. There are several ways to sort in Java there are Selection, Merge, and Insertion Sorts and each are differently efficient and are used for different reasons.

Merge Sort
Algorithm:

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++;

        }

 

    }

}




There are different reasons why anyone would use Merge Sort instead of other kinds:

1) it is the most efficient type of sorting for bigger arrays of numbers.

2) it offers performance just bellow Quick Sort but uses less memory space.

Merge Sort Demo.

However it takes more knowledge of coding and a greater understanding of algorithms, and it takes a considerable amount of memory space, if used frequently.