Java Merge Sort Algorithm Implementation? Detailed Explanation and Complete Tutorial

On Crunchify, we have written so far 500+ Java and Spring MVC technology related tutorials. Learning new stuff never bored me. I like learning new stuff every day and I believe it’s the same for my readers :).

As you may have seen before Bubble Sort Algorithm, Selection Sort Algorithm and Insertion Sort Algorithm is very popular among various interviews.

In this tutorial, we will go over Merge Sort Algorithm.

Merge sort algorithm is very simple. Divide an array into half when it reaches to only one level then sort it. Next step is to merge it in sequence. Basically it’s divide and conquer approach.

Here is a simple explanation about merge sort on how to it will divide and merge elements.

Let’s answer all of below questions today in this tutorial:

• What is the merge sort algorithm?
• What is the implementation of merge?
• Mergesort in Java – Tutorial
• merge sort java code

We are going to perform below steps:

1. Create crunchifyArray with size 10
2. Fill 10 random Integers into array
3. Print initial Array
4. Perform Merge Sort
5. Print final Array after merge sort

Here is a Java Code:

package crunchify.com.tutorial;

import java.util.*;

/**
 * @author Crunchify.com Merge Sort Algorithm in Java
 * 
 */

public class CrunchifyMergeSortAlgorithm {
        public static Integer[] crunchifyArray = new Integer[10];;
        public static int iteration = 1;

        // Divide and Merge
        public static void crunchifyMergeSort(Integer[] crunchifyArray) {
                Integer[] tempArray = new Integer[crunchifyArray.length];

                // recursively perform merge sort
                crunchifyMergeSort(crunchifyArray, tempArray, 0, crunchifyArray.length - 1);

        }

        // Idea is simple:
        // First divide whole array into 2 part
        // Divide each array into another 2 part
        // Once it reaches to only 1 elements in each side tree, just sort it
        // Merge backward the same way to get complete sorted array
        private static void crunchifyMergeSort(Integer[] crunchifyArray, Integer[] tempArray, int myLeft, int myRight) {

                if (myLeft < myRight) {
                        int center = (myLeft + myRight) / 2;
                        crunchifyMergeSort(crunchifyArray, tempArray, myLeft, center);
                        crunchifyMergeSort(crunchifyArray, tempArray, center + 1, myRight);
                        crunchifyMerge(crunchifyArray, tempArray, myLeft, center + 1, myRight);
                }
        }

        // Merge Sort Algorithm
        private static void crunchifyMerge(Integer[] crunchifyArray, Integer[] tempArray, int left, int myRight,
                        int rightMost) {
                int leftEnd = myRight - 1;
                int k = left;
                int num = rightMost - left + 1;

                while (left <= leftEnd && myRight <= rightMost)
                        if (crunchifyArray[left].compareTo(crunchifyArray[myRight]) <= 0)
                                tempArray[k++] = crunchifyArray[left++];
                        else
                                tempArray[k++] = crunchifyArray[myRight++];

                while (left <= leftEnd)
                        tempArray[k++] = crunchifyArray[left++];

                while (myRight <= rightMost)
                        tempArray[k++] = crunchifyArray[myRight++];

                for (int i = 0; i < num; i++, rightMost--)
                        crunchifyArray[rightMost] = tempArray[rightMost];

                System.out.print("Iteration # " + iteration + " ===> ");
                crunchifyPrint();
                iteration++;

        }

        // Get Random Integer in Java
        public static Integer getRandomIntegers() {

                Random crunchifyRandom = new Random();
                int myNumber = crunchifyRandom.nextInt(150);
                return myNumber;
        }

        // Simply Print Arrays
        public static void crunchifyPrint() {
                for (int n : crunchifyArray) {
                        System.out.print(" " + n + "  ");
                }
                System.out.print("\n");
        }

        // Main Method
        public static void main(String[] args) {

                for (int i = 0; i < crunchifyArray.length; i++) {
                        crunchifyArray[i] = getRandomIntegers();
                }

                System.out.print("Here is our initial array: ");
                crunchifyPrint();
                System.out.println();

                // Perform actual sorting
                crunchifyMergeSort(crunchifyArray);

                System.out.println();
                System.out.print("Here is an array after Merge Sort: ");
                crunchifyPrint();
        }
}

Eclipse Console Output:

Here is our initial array:  45   53   10   50   48   8   106   77   44   108  

Iteration # 1 ===>  45   53   10   50   48   8   106   77   44   108  
Iteration # 2 ===>  10   45   53   50   48   8   106   77   44   108  
Iteration # 3 ===>  10   45   53   48   50   8   106   77   44   108  
Iteration # 4 ===>  10   45   48   50   53   8   106   77   44   108  
Iteration # 5 ===>  10   45   48   50   53   8   106   77   44   108  
Iteration # 6 ===>  10   45   48   50   53   8   77   106   44   108  
Iteration # 7 ===>  10   45   48   50   53   8   77   106   44   108  
Iteration # 8 ===>  10   45   48   50   53   8   44   77   106   108  
Iteration # 9 ===>  8   10   44   45   48   50   53   77   106   108  

Here is an array after Merge Sort:  8   10   44   45   48   50   53   77   106   108  

Try debugging program carefully to understand two methods crunchifyMergeSort and crunchifyMerge. Let me know if you have any questions or problem running above code.

Big O Notation / What is a Merge Sort Algo Complexity?

• n*log(n)

Merge Sort Best Case Scenario Complexity?

• O(n) in case of already sorted input

The post Java Merge Sort Algorithm Implementation? Detailed Explanation and Complete Tutorial appeared first on Crunchify.