Merge Sort Java

Hey guys!! Welcome to flower brackets blog. Today in this post you will learn merge sort java. Basically merge sort java program is used to sort group of objects.

merge sort java

What is merge sort?

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

Also Read – Bubble Sort Java Program

In mergesort original elements are divided into smaller elements of data to sort the given integer elements.

Let’s learn merge sort explanation with an merge sort example,

Given an array of items merge sort will sort them in a ascending order. We are going to use integers.

So let’s say we want to sort a small list of four integers 2, 4, 3 and 1.

Merge Sort Java

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,

Example: merge sort java

import java.util.Scanner;

// class java merge sort
public class JavaMergeSort
{
   // merge sort algorithm function

   public static void sorting(int x[], int low, int high)
   {
      int M = high - low;

      if(M <= 1)
         return;

      int middle = low + M / 2;

      // recursive merge sort
      sorting(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];
      }
   }

   // merge sort algorithm java main method starts here
   public static void main(String[] args)
   {
      Scanner sc = new Scanner(System.in);
      System.out.println("Java Merge Sort\n");
      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 method
      sorting(array, 0, n);

      // Printing sorted array
      System.out.println("Integers after sorting: ");
      for(i = 0;i < n;i++)
      System.out.print(array[i] + " ");
      System.out.println();
   }
}

Output :

Java Merge Sort

Java merge sort

Please enter number of integers : 6

Please enter 6 integer elements : 33 00 55 11 22 44
Integers 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 algorithm java or merge sort pseudocode,

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];
 
 
      // merge sort example java
 
      // 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 java
   void sortmerge(int mergeArray[], int p, int r)
   {
      if(p < r)
      {
         // middle point
         int m = (p + r) / 2;
 
         // sorting into 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 – How To Sort Elements In Array In Ascending Order 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).


conclusion

That’s it guys. This was all about merge sort java. I hope you have understood merge sort implementation java.

You can subscribe to my blog flower brackets if you haven’t already.

Do share this post if you like.

You May Also Like