Merge Sorting Algorithms in Java

Updated July 4, 2023

Introduction to Merge Sorting Algorithms in Java

Merge Sorting Algorithms are very important in Computer Science. The output of sorting is to arrange the elements of a list to a certain order (either ascending or descending). Merge sort is one of the most efficient sorting algorithms available as it is based on the concept of divide and conquers. As the name suggests, first divide the bigger problem into small problems, then solve the smaller problems in order to solve the bigger problem. In this article, we will discuss Merge Sorting Algorithms in Java.

Conceptually, Merge sort is a combination of two basic algorithms called MERGE and MERGE_SORT, which works as follows:

1. Divide the unsorted list into n number of single-item sub lists (n is the total number of elements in the unsorted list).
2. Repeatedly merge sublists into sorted sublists until there is only one sorted list.

Implementation of Merge Sorting Algorithms in Java

The MERGE algorithm is the procedure of combining two sorted lists into one sorted list.

Example: Suppose there are two lists i.e. List 1 {6,3} and List 2 {3,1,9}.

1. First, sort both the lists.

List 1

List 2

Now, we will apply a merging technique to it.

2. Then, we will create a new list of size m+n where m is the number of elements in List 1 and n is the number of elements in List 2.

List 3

In our case m=2 and n=3, so m+n= 5.

3. Now, we have a two-pointer. A first pointer pointing at the first position of List 1 and a Second pointer pointing at the first position of List 2.

4. Then, we will compare the value of both pointers. For the pointer with lesser value, copy that element into List 3 and move the pointer to the right of the list with a smaller value and the resultant list (i.e., List 1 and List 3).

5. Similarly, perform step 4 again and again.

Further traversing…..

Algorithm & Pseudocode

The two Algorithms used in Merge Algorithm are:

• The MERGE(ARR, F, M, L) is a process that assumes the following:

1. ARR[F ….M] and ARR[M+ 1….L] are sorted lists.
2. Merges the two sorted sub-lists into one ARR[F….L].

• SORT(ARR[], F, L) //here F is the first and L is the last index of the array.

If  ( L >  1 )

1. Find the middle point to divide the list into two halves:

middle  M = (F +L)/2

2. Call Merge Sort for the first half:

Call  SORT(ARR, 1, M)

3. Call Merge Sort for the second half:

Call  SORT(ARR, M+ 1, L)

4. Merge the halves sorted in step 2 and 3:

Call MERGE(ARR, L, M, R) 

Example

Let us take an example of an array  ARR {10,6,8,5,7,3,4}. We will use the Merge Algorithm to sort the Array using its Divide and Conquer Technique. We can see the below figure that the Array is recursively divided into two halves till the size becomes 1. Once the size becomes 1, we call merged processes and merging lists back until the complete list is merged.

Program Code:

import java.util.Scanner;
public class mergeSort {
// merges two sublists of arr[].
// first list is arr[l..m]
// second list is arr[m+1..r]
void mergeAlgo(int arr[], int l, int m, int r)
{
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L[] = new int [n1];
int R[] = new int [n2];
// copy data to temp arrays
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// copy remaining elements of L[] if any
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// copy remaining elements of R[] if any
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// main function that sorts arr[l..r] using mergeAlgo()
void sort(int arr[], int l, int r)
{
if (l < r)
{
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
}
}
/* A function to print list of size n */
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[])
{
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr[] = new int[N];
for(int i=0; i<arr.length; i++) {
arr[i] = myObj.nextInt();
}
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
}
}

Output:

Conclusion – Merge Sorting Algorithms in Java

Merge sort best, worst, and average-case time complexities are the same, which makes it a more efficient algorithm. It works faster than other sorting techniques. Merge sort can be applied to files of any size. It is highly parallelizable due to the use of the divide-and-conquer method. To develop strong basics in computer science, you are advised to understand different sorting algorithms thoroughly.

Recommended Articles

This is a guide to Merge Sorting Algorithms in Java. Here we discuss the Implementation of Merge Sorting Algorithms in java and Algorithm & Pseudocode with example. You can also go through our other suggested articles–

1. Selection Sort in Java
2. Merge Sort in JavaScript
3. Quick Sorting Algorithms in Java
4. Sorting in C#