How to write a java program to implement merge sort??

               Sorting. It is a way of arranging data elements. There are many algorithms to perform sorting. One of the efficient algorithms is merge sort.

Who invented merge sort?

John von Neumann invented merge sort in 1945.

How the merge sort algorithm works?

              This algorithm uses divide and conquer concept.

• ·       First, divide the entire list into sub lists. Each sub list should contain at least one element.
• ·       Next, check each sub list and sort it separately. Repeat this process for all sub lists.
• ·       Finally, all the sorted sub lists are merged.
• Here, is the java program to implement merge sort.

//Java Program to implement merge sort.

import java.util.Arrays;

public class MergeSort {

      void merge(int array[], int a, int b, int c) {

        // Find sizes of two sub lists.

        int n1 = b - a + 1;

        int n2 = c - b;

        // creating Two  integer temp arrays

        int F[] = new int[n1];

        int S[] = new int[n2];

        // Loop to store data in temp arrays

        for (int i = 0; i < n1; ++i)

            F[i] = array[a + i];

        for (int j = 0; j < n2; ++j)

            S[j] = array[b + 1 + j];

        // Initialize the values of first and second sub lists

        int i = 0, j = 0;

        // Initialize the value of merged sub lists

        int k = a;

        while (i < n1 && j < n2) {

            if (F[i] <= S[j]) {

                array[k] = F[i];

                i++;

            } else {

                array[k] = S[j];

                j++;

            }

            k++;

        }

        // If there is any remaining elements in F[] then copy the elements. 

        while (i < n1) {

            array[k] = F[i];

            i++;

            k++;

        }

 

        //  If there is any remaining elements in S[] then copy the elements

        while (j < n2) {

            array[k] = S[j];

            j++;

            k++;

        }

    }

    // Merge sort begins

    void sort(int array[], int l, int r) {

        if (l < r) {

            // calculate the middle element

            int m = (l + r) / 2;

            // sort first and second half sublists.

            sort(array, l, m);

            sort(array, m + 1, r);

 

            // Merge the sublists

            merge(array, l, m, r);

        }

    }

    // Displaying the array elements

    static void printArray(int array[]) {

        int n = array.length;

        for (int i = 0; i < n; ++i)

            System.out.print(array[i] + " ");

        System.out.println();

    }

 

    // main function

    public static void main(String args[]) {

        int arr[] = {12, 11, 13, 5, 6, 7};

        System.out.println("Input array");

        printArray(arr);

        MergeSort ob = new MergeSort();

        ob.sort(arr, 0, arr.length - 1);

        System.out.println("\nThe array after merge sort");

        printArray(arr);

    }

}

• ·       Save this program as “MergeSort.java”.
• ·       Open a command prompt. Compile the program.
• ·       Run the program like as follows.

 This is way of implementing merge sort algorithm in java.