How to Implement Merge Sort in Java

The programmers often come across various algorithms for performing data-related tasks. The “Merge Sort” is one such sorting algorithm in Java that is preferred while dealing with linked lists. This algorithm is suitable for large and complex lists but operates slowly on smaller lists. Moreover, it can also be used to sort the files within external storage systems i.e., hard drives, etc, and is recommended when there is a consideration for data stability.

Contents Overview

• What is Merge Sort in Java?
• Working of the “Merge Sort” Algorithm
• Algorithm of Merge Sort
• Merge Sort Complexity
• How to Implement Merge Sort in Java?
• Advantages of Merge Sort
• Use-Cases of Merge Sort
• Limitations of Merge Sort

What is Merge Sort in Java?

The “Merge Sort” algorithm is based on the “divide and conquer” approach where a query is further divided into sub-queries. Each subquery is solved separately; finally, all the subqueries are merged/combined in a sorted form. 

“Divide and Conquer” Approach

Below is the explanation of this algorithm approach that combines all these steps:

Step 1: Divide

Decompose the given larger problem into smaller subproblems.

Step 2: Conquer

Use the function recursively to solve each of the subproblems.

Step 3: Combine

Compose the solution to the smaller subproblems of the larger problem.

Working of the “Merge Sort” Algorithm

In the above illustration, it can be seen that the given larger array of elements is divided into sub-arrays till the point where the elements can not be further divided. After that, the elements are sorted and merged in ascending order appropriately.

Algorithm of Merge Sort

Below is the “Merge Sort” algorithm based on which the sorting will be performed:

merge(array[], sizeMin, sizeMax)

if sizeMin< sizeMax
  set mid = (sizeMin + sizeMax)/2
  merge(array, sizeMin, mid)
  merge(array, mid + 1, sizeMax)
  mergeSortArrays(array, sizeMin, mid, sizeMax)
  end of if
 
END merge

Algorithm Explanation

In this algorithm, the function “merge()” contains the array i.e., “array[]” to sort, its first element i.e., “sizeMin” and its last element i.e., “sizeMax”, respectively. 

Based on these elements, the middle element will be returned and this function will be called recursively to sort the two sub-arrays i.e., “merge(array, sizeMin, mid)” and “merge(array, mid + 1, sizeMax)”. Finally, a final sorted array will be returned by invoking the “mergeSortArrays()” function.

Merge Sort Complexity

Following are the complexities of Merge Sort:

Time Complexity

Case	Occurrence	Time Complexity
Best Case	When the array is already sorted i.e., no sorting is needed.	O(n*logn)
Average Case	When the array elements are mixed up i.e., neither in proper ascending nor in descending order.	O(n*logn)
Worst Case	When the array elements need to be sorted in completely reverse order.	O(n*logn)

Space Complexity

The Space Complexity for merge sort is “O(n)”. It is because an extra variable is needed for swapping.

How to Implement Merge Sort in Java?

The “Merge Sort” algorithm can be implemented by declaring two functions: one for fetching the middle element and sorting the sub-arrays. This function is called recursively for each sub-array. The other function returns the resultant sorted array.

The below code snippets explain the stated concept:

Function for Merging the SubArrays

void mergeSortArrays(int array[], int a, int b, int c) {
  int x = b - a + 1;
  int y = c - b;
  int leftArray[] = new int[x];
  int rightArray[] = new int[y];
  for (int i = 0; i < x; i++)
    leftArray[i] = array[a + i];
    for (int j = 0; j < y; j++)
      rightArray[j] = array[b + 1 + j];
      int i, j, k;
      i = 0;
      j = 0;
      k = a;
    while (i < x && j < y) {
    if (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
}      else {
array[k] = rightArray[j];
j++;
}
k++;
}
while (i < x) {
  array[k] = leftArray[i];
  i++;
  k++;
}
while (j < y) {
  array[k] = rightArray[j];
  j++;
  k++;
}}

Code Explanation

• The defined function “mergeSortArrays()” contains the given array, its first, middle, and last elements as its parameters to be passed as arguments.
• In its definition, calculate the size of both the subarrays to be merged and create two different arrays of the same size accordingly.
• In the next step, fill the left and right subarrays with the passed array elements using the “for” loop.
• Now, initialize the template variables to merge sort the passed array elements in ascending order.
• This can be done by comparing the left and right array elements filled with the elements before.
• Lastly, use the “while” loop to copy the remaining elements of the left and right arrays, if any.

Function for Dividing the Array into Subarrays

void merge(int array[], int sizeMin, int sizeMax) {
  if (sizeMin < sizeMax) {
    int mid = (sizeMin + sizeMax) / 2; //1.5
    merge(array, sizeMin, mid);//0, 1.5
    merge(array, mid + 1, sizeMax);//2.5,3
    mergeSortArrays(array, sizeMin, mid, sizeMax);
}}

Code Explanation

• Define the function “merge()” that comprises the given array, its first elements, and its last element as its parameter, respectively.
• In the function definition, check if the first element is less than the last element and get the middle element in the array upon the satisfied condition.
• Moving forward, call this function recursively to create two subarrays: one from the first element to the middle and the other from the middle to the last element.
• Finally, access the “mergeSortArrays()” function to merge the subarrays after sorting.

Main Code

public static void main(String args[]) {
  int[] array = {5, 4, 3, 2, 9, 7};
  System.out.println("Given Unsorted Array Elements: ");
  for (int i=0;i<array.length;i++) {
    System.out.println(array[i]);
}
  Mergesort ob = new Mergesort();
  ob.merge(array, 0, array.length - 1);
  System.out.println("Array Elements After Merge Sorting: ");
  System.out.println(Arrays.toString(array));
}

Code Explanation

• Declare an integer array containing the given elements and display it via iteration using the “for” loop.
• Now, create a class instance and invoke the “merge()” function using this instance/object.
• In this function, pass the defined array, its first element index, and the last index as the function arguments.
• Lastly, return the array as a string using the “toString()” method.

Entire Code

package jbArticles;
import java.util.Arrays;
public class Mergesort {
  void mergeSortArrays(int array[], int a, int b, int c) {
    int x = b - a + 1; //2.5
    int y = c - b;//1.5
    int leftArray[] = new int[x];
    int rightArray[] = new int[y];
    for (int i = 0; i < x; i++)
      leftArray[i] = array[a + i];
      for (int j = 0; j < y; j++)
  rightArray[j] = array[b + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = a;
while (i < x && j < y) {
  if (leftArray[i] <= rightArray[j]) {
    array[k] = leftArray[i];
    i++;
}          else {
    array[k] = rightArray[j];
    j++;
}
    k++;
}
  while (i < x) {
    array[k] = leftArray[i];
    i++;
    k++;
}
    while (j < y) {
array[k] = rightArray[j];
j++;
k++;
}}
void merge(int array[], int sizeMin, int sizeMax) {
  if (sizeMin < sizeMax) {
    int mid = (sizeMin + sizeMax) / 2; //1.5
    merge(array, sizeMin, mid);//0, 1.5
    merge(array, mid + 1, sizeMax);//2.5,3
    mergeSortArrays(array, sizeMin, mid, sizeMax);
}}
public static void main(String args[]) {
  int[] array = {5, 4, 3, 2, 9, 7};
  System.out.println("Given Unsorted Array Elements: ");
  for (int i=0;i<array.length;i++) {
    System.out.println(array[i]);
}
  Mergesort ob = new Mergesort();
  ob.merge(array, 0, array.length - 1); //0,3
  System.out.println("Array Elements After Merge Sorting: ");
  System.out.println(Arrays.toString(array));
}}

Output

Useful Consideration

If there is a requirement to sort the array in descending order instead, use the following code line in the “if” statement:

(leftArray[i] >= rightArray[j])

Demonstration

Advantages of Merge Sort

• It is a stable algorithm. It is such that it manages the relative order of the equal elements.
• It has good performance on large datasets.
• This algorithm can use multiple processors/threads.

Use-Cases of Merge Sort

• It is suitable for sorting large datasets.
• It is commonly used in external sorting where the data that needs to be sorted is too large to be contained in memory.
• It can sort different types of data such as partially sorted, or completely unsorted data.

Limitations of Merge Sort

• This algorithm performs slowly on small datasets.
• It is not an in-place sorting algorithm. This implies that it needs extra/additional memory to contain the sorted data.
• It does not need extra memory to contain the merged subarrays while sorting.
• It runs the operational steps even if the default list/array is already sorted.

Conclusion

The “Merge Sort” algorithm is based on the “divide and conquer” approach. This algorithm can be implemented by dividing the given array into subarrays, sorting each subarray individually, and then merging the sorted subarrays as the final sorted single array. It is one of the most efficient sorting algorithms suitable for solving complex datasets.