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:
- Create
crunchifyArray
with size 10 - Fill 10 random Integers into array
- Print initial Array
- Perform Merge Sort
- 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