Hey guys!! Welcome to flower brackets blog. Today in this post you will learn merge sort java.

Merge sort is basically an algorithm. Widely known as divide and conquer algorithm.

Also read – bubble sort java program

In merge sort, original elements are divided into smaller elements of data to sort the given integer elements. Let’s learn merge sort with an example.

Given an array of items merge sort will sort in an ascending order. Here we are going to use integers as elements. So let’s say we want to sort a small list 2, 4, 3 and 1.

One way to sort them would be to break the list in half into two smaller lists. Now 2 and 4 is already sorted, 3 and 1 we have to swap places.

Now we have two smaller lists in sorted order and then merge those two smaller lists back together.

So to do that we can compare the first two numbers. Since we know those are the two smallest number.

This leftmost number is the smallest number in each list. So we compare 2 to 1. 1 is smaller so we will add 1 back to the main list first and then we compare 2 to 3.

Also read – how to sort hashmap by values in java

2 is the smaller so we add 2 to the main list. Then we compare 3 to 4, 3 is the smaller number so we add 3 to main list.

We are done with the right list. Now all we have left is 4. So we add that to the main list.

Now we have a sorted list of four digits. That in a nutshell is how merge sort works.

Below we have merge sort implementation java,

import java.util.Scanner; public class JavaMergeSort { public static void sorting(int x[], int low, int high) { int M = high - low; if(M <= 1) return; int middle = low + M / 2; // recursive sortsorting(x, low, middle);sorting(x, middle, high); // now merge two sorted subarrays int temp[] = new int[M]; int m = low; int n = middle; for(int y = 0; y < M; y++) { if(m == middle) { temp[y] = x[n++]; } else if(n == high) { temp[y] = x[m++]; } else if(x[n] < x[m]) { temp[y] = x[n++]; } else { temp[y] = x[m++]; } } for(int y = 0; y < M; y++) { x[low + y] = temp[y]; } } // main method public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n; int i; // User entering number of elements System.out.println("Please enter number of integers: "); n = sc.nextInt(); // Creating array of n integers int array[] = new int[n]; // Receiving integers System.out.println("\nPlease enter " + n + " integer elements: "); for(i = 0;i < n;i++) { array[i] = sc.nextInt(); } // Call sorting methodsorting(array, 0, n); // Printing sorted array System.out.println("After sorting : "); for(i = 0;i < n;i++) System.out.print(array[i] + " "); System.out.println(); } }

**Output :**

Please enter number of integers : 6

Please enter 6 integer elements : 33 00 55 11 22 44

After sorting : 0 11 22 33 44 55

#### Merge sort java : another way

Here we are going to learn another way to execute merge sort,

public class MergeSort { void merge(int mergeSortArray[], int a, int b, int c) { // here we are finding size of subarray int num1 = b - a + 1; int num2 = c - b; // temporary arrays int left[] = new int[num1]; int right[] = new int[num2]; // copying data for(int m = 0; m < num1; ++m) left[m] = mergeSortArray[a + m]; for(int n = 0; n < num2; ++n) right[n] = mergeSortArray[b + 1 + n]; // this is initial index of first and second subarray int m = 0, n = 0; // initial index of merged subarry array int g = a; while(m < num1 && n < num2) { if(left[m] <= right[n]) { mergeSortArray[g] = left[m]; m++; } else { mergeSortArray[g] = right[n]; n++; } g++; } while(m < num1) { mergeSortArray[g] = left[m]; m++; g++; } while(n < num2) { mergeSortArray[g] = right[n]; n++; g++; } } // merge sort method void sortmerge(int mergeArray[], int p, int r) { if(p < r) { // middle point int m = (p + r) / 2; // sorting first and second halves sortmerge(mergeArray, p, m); sortmerge(mergeArray, m+1, r); // now merge the sorted halves merge(mergeArray, p, m, r); } } // printing array static void printArray(int arr[]) { int n = arr.length; for(int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } public static void main(String[] args) { System.out.println("Before sorting numbers : "); int arr[] = {13, 12, 14, 4, 7, 8};printArray(arr); MergeSort ms = new MergeSort(); ms.sortmerge(arr,0 ,arr.length - 1); System.out.println("\nAfter sorting numbers : "); System.out.println("\nSorted array : ");printArray(arr); } }

**Output :**

Before sorting numbers :

13 12 14 4 7 8

After sorting numbers :

Sorted array :

4 7 8 12 13 14

**Time and space complexity of merge sort**

Let us now try to understand time and space complexity of merge sort. Let us first try to analyze the time complexity,

Mergesort(A) { n ← length(A) if(n > 2) return middle ← n / 2 left ← array of size(middle) right ← array of size(n - middle) for i ← 0 to middle - 1 left[i] ← A[i] for i ← middle to n - 1 right[i - middle] ← A[i] MergeSort(left) MergeSort(right) Merge(left, right, A) }

We have the pseudo-code for merge sort algorithm here. Let’s say the time taken for an array of size “n” by merge sort algorithm will be T(n).

Let us now see how we can find an approximate expression for this T(n).

Talking about some of the fundamentals of time analysis, we always try to approximate the worst case and we try to see the rate of growth of time taken for very high values of “n” and then we try to classify the time expression as big-o or theta of some function.

Also read – sort array in java

Here in this algorithm, let’s say when we are executing for n > 1, all those statements (as you can see in pseudo code above) they are simple statements.

Here simple statements are statements that have simple operations like arithmetic or logical statements and simple statements execute in constant time.

So let’s say these set of statements in worst case will take some constant time c1.

If there are no loops or function calls and there are only simple statements, then the time taken will not be a function of the input size.

Now these two loops, these two assignments,

for i ← 0 to middle - 1 left[i] ← A[i] for i ← middle to n - 1 right[i - middle] ← A[i]

Here will have same cost and these two loops together will run “n” times.

So, we can say that they will together cost us some constant, say, “c2” is the cost of executing one of the statements, then the cost will be ( c2 * n ).

Sometimes we directly speak in terms of the asymptotic notations only. Like we can directly say that this (above code) particular segment of the code is theta(n) in terms of time complexity.

But let’s talk like this, that this will execute in ( c2 * n ) where c2 is some constant and then we have this recursive call “MergeSort” for left

MergeSort(left)

If we are saying that we will take T(n) time for MergeSort for an array of size n, the left will be an array of size n / 2.

So this will be T(n/2) cost for us. And then we have another “MergeSort” call that will again be T(n/2).

Also read – sort string array java

And then we have a call to “Merge”. Now for this one, we will have to look at the merge function, what is the complexity of merge function.

If you remember the merge function, it was picking up one element from either left or right at a time and writing it in another array.

So, all loops were running for total length of left subarray plus total length of right subarray. So, in all , loops were running for “n” times.

If you would analyze the running time for merge function also, it will be of some form, like some constant times “n” plus some other constant.

So, space complexity of merge sort is theta n (θ n). Time complexity of merge sort is O(n log n).