Merge Sort In Java – Program To Implement MergeSort

This Tutorial Explains what is Merge Sort in Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Examples of Iterative & Recursive MergeSort:

Merge sort technique uses a “Divide-and-Conquer” strategy. In this technique, the data set that is to be sorted is divided into smaller units to sort it.

=> Read Through The Easy Java Training Series.

Merge Sort In Java

For example, if an array is to be sorted using mergesort, then the array is divided around its middle element into two sub-arrays. These two sub-arrays are further divided into smaller units until we have only 1 element per unit.

Once the division is done, this technique merges these individual units by comparing each element and sorting them when merging. This way by the time the entire array is merged back, we get a sorted array.

In this tutorial, we will discuss all the details of this sorting technique in general including its algorithm and pseudo codes as well as the implementation of the technique in Java.

MergeSort Algorithm In Java

Following is the algorithm for the technique.

#1) Declare an array myArray of length N

#2) Check if N=1, myArray is already sorted

#3) If N is greater than 1,

• set left = 0, right = N-1
• compute middle = (left + right)/2
• Call subroutine merge_sort (myArray,left,middle) => this sorts first half of the array
• Call subroutine merge_sort (myArray,middle+1,right) => this will sort the second half of the array
• Call subroutine merge (myArray, left, middle, right) to merge arrays sorted in the above steps.

#4) Exit

As seen in the algorithm steps, the array is divided into two in the middle. Then we recursively sort the left half of the array and then the right half. Once we individually sort both the halves, they are merged together to obtain a sorted array.

Merge Sort Pseudo Code

Let’s see the pseudo-code for the Mergesort technique. As already discussed since this is a ‘divide-and-conquer’ technique, we will present the routines for dividing the data set and then merging the sorted data sets.

procedure mergesort( var intarray as array )
   if ( n == 1 ) return intarray

   var lArray as array = intarray[0] ... intarray [n/2]
   var rArray as array = intarray [n/2+1] ... intarray [n]

   lArray = mergesort(lArray )
   rArray = mergesort(rArray )

   return merge(lArray, rArray )
end procedure

procedure merge( var l_array as array, var r_array as array )

   var result as array
   while (l_array and r_array have elements )
      if (l_array [0] > r_array [0] )
         add r_array [0] to the end of result
         remove r_array [0] from r_array
      else
         add l_array [0] to the end of result
         remove l_array [0] from l_array
      end if
   end while
   
   while (l_array has elements )
      add l_array [0] to the end of result
      remove l_array [0] from l_array
   end while
   
   while (r_array has elements )
      add r_array [0] to the end of result
      remove r_array [0] from r_array
   end while
   
   return result
	
end procedure

In the above pseudo-code, we have two routines i.e. Mergesort and merge. The routine Mergesort splits the input array into an individual array that is easy enough to sort. Then it calls the merge routine.

The merge routine merges the individual sub-arrays and returns a resultant sorted array. Having seen the algorithm and pseudo-code for Merge sort, let’s now illustrate this technique using an example.

MergeSort Illustration

Consider the following array that is to be sorted using this technique.

Now according to the Merge sort algorithm, we will split this array at its mid element into two sub-arrays. Then we will continue splitting the sub-arrays into smaller arrays till we get a single element in each array.

Once each sub-array has only one element in it, we merge the elements. While merging, we compare the elements and ensure that they are in order in the merged array. So we work our way up to get a merged array that is sorted.

The process is shown below:

As shown in the above illustration, we see that the array is divided repeatedly and then merged to get a sorted array. With this concept in mind, let’s move onto the implementation of Mergesort in Java programming language.

Merge Sort Implementation In Java

We can implement the technique in Java using two approaches.

Iterative Merge Sort

This is a bottom-up approach. The sub-arrays of one element each are sorted and merged to form two-element arrays. These arrays are then merged to form four-element arrays and so on. This way the sorted array is built by going upwards.

The below Java example shows the iterative Merge Sort technique.

import java.util.Arrays;

class Main
{
	// merge arrays : intArray[start...mid] and intArray[mid+1...end]
	public static void merge(int[] intArray, int[] temp, int start, int mid, int end)
	{
		int k = start, i = start, j = mid + 1;

		// traverse through elements of left and right arrays
		while (i <= mid && j <= end) {
			if (intArray[i] < intArray[j]) {
				temp[k++] = intArray[i++];
			} else {
				temp[k++] = intArray[j++];
			}
		}

		// Copy remaining elements
		while (i <= mid) {
			temp[k++] = intArray[i++];
		}

		// copy temp array back to the original array to reflect sorted order
		for (i = start; i <= end; i++) {
			intArray[i] = temp[i];
		}
	}
// sorting intArray[low...high] using iterative approach
	public static void mergeSort(int[] intArray)
	{
		int low = 0;
		int high = intArray.length - 1;

		// sort array intArray[] using temporary array temp
		int[] temp = Arrays.copyOf(intArray, intArray.length);

		// divide the array into blocks of size m
		// m = [1, 2, 4, 8, 16...]
		for (int m = 1; m <= high - low; m = 2*m)
		{
			for (int i = low; i < high; i += 2*m)
			{
				int start = i;
				int mid = i + m - 1;
				int end = Integer.min(i + 2 * m - 1, high);
                //call merge routine to merge the arrays
				merge(intArray, temp, start, mid, end);
			}
		}
	}

	public static void main(String[] args)
	{
	    //define array to be sorted
		int[] intArray = { 10,23,-11,54,2,9,-10,45 };
        //print the original array
		System.out.println("Original Array : " + Arrays.toString(intArray));
		//call mergeSort routine
		mergeSort(intArray);
		//print the sorted array
		System.out.println("Sorted Array : " + Arrays.toString(intArray));
	}
}

Output:

Original Array : [10, 23, -11, 54, 2, 9, -10, 45]
Sorted Array : [-11, -10, 2, 9, 10, 23, 45, 54]

Recursive Merge Sort

This is a top-down approach. In this approach, the array to be sorted is broken down into smaller arrays until each array contains only one element. Then the sorting becomes easy to implement.

The following Java code implements the recursive approach of the Merge sort technique.

import java.util.Arrays; 
public class Main { 
    public static void merge_Sort(int[] numArray) { 
        //return if array is empty
        if(numArray == null) { 
            return; 
        } 
          if(numArray.length > 1) { 
            int mid = numArray.length / 2; //find mid of the array
  
            // left half of the array 
            int[] left = new int[mid]; 
            for(int i = 0; i < mid; i++) { 
                left[i] = numArray[i]; 
            } 
            // right half of the array 
            int[] right = new int[numArray.length - mid]; 
            for(int i = mid; i < numArray.length; i++) { 
                right[i - mid] = numArray[i]; 
            } 
            merge_Sort(left);   //call merge_Sort routine for left half of the array 
            merge_Sort(right);   // call merge_Sort routine for right half of the array
  
            int i = 0; 
            int j = 0; 
            int k = 0; 
              // now merge two arrays
            while(i < left.length && j < right.length) { 
                if(left[i] < right[j]) { 
                    numArray[k] = left[i]; 
                    i++; 
                } 
                else { 
                    numArray[k] = right[j]; 
                    j++; 
                } 
                k++; 
            } 
         
   // remaining elements 
            while(i < left.length) { 
                numArray[k] = left[i]; 
                i++; 
                k++; 
            } 
            while(j < right.length) { 
                numArray[k] = right[j]; 
                j++; 
                k++; 
            } 
        } 
    }
public static void main(String[] args) { 
        int numArray[] = {10, 23, -11, 54, 2, 9, -10, 45}; 
        int i=0; 
        //print original array       
        System.out.println("Original Array:" + Arrays.toString(numArray)); 
        //call merge_Sort routine to sort arrays recursively
        merge_Sort(numArray); 
        //print the sorted array
        System.out.println("Sorted array:" + Arrays.toString(numArray)); 
   } 
} 
  

Output:

Original Array:[10, 23, -11, 54, 2, 9, -10, 45]
Sorted array:[-11, -10, 2, 9, 10, 23, 45, 54]

In the next section, let’s switch from arrays and use the technique to sort the linked list and array list data structures.

Sort Linked List Using Merge Sort In Java

Mergesort technique is the most preferred one for sorting linked lists. Other sorting techniques perform poorly when it comes to the linked list because of its mostly sequential access.

The following program sorts a linked list using this technique.

import java.util.*;
// A singly linked list node
class Node
{
	int data;
	Node next;

	Node(int data, Node next) {
		this.data = data;
		this.next = next;
	}
};

class Main {
    //two sorted linked list are merged together to form one sorted linked list
	public static Node Sorted_MergeSort(Node node1, Node node2) {
		//return other list if one is null
		if (node1 == null)
			return node2;

		else if (node2 == null)
			return node1;

		Node result;

		// Pick either node1 or node2, and recur
		if (node1.data <= node2.data) {
			result = node1;
			result.next = Sorted_MergeSort(node1.next, node2);
		}
		else {
			result = node2;
			result.next = Sorted_MergeSort(node1, node2.next);
		}

		return result;
	}
//splits the given linked list into two halves
	public static Node[] FrontBackSplit(Node source) {
		// empty list
		if (source == null || source.next == null) {
			return new Node[]{ source, null } ;
		}

		Node slow_ptr = source;
		Node fast_ptr = source.next;

		// Advance 'fast' two nodes, and advance 'slow' one node
		while (fast_ptr != null) {
			fast_ptr = fast_ptr.next;
			if (fast_ptr != null) {
				slow_ptr = slow_ptr.next;
				fast_ptr = fast_ptr.next;
			}
		}

		// split the list at slow_ptr just before mid
		Node[] l_list = new Node[]{ source, slow_ptr.next };
		slow_ptr.next = null;

		return l_list;
	}

	// use Merge sort technique to sort the linked list
	public static Node Merge_Sort(Node head) {
		// list is empty or has single node
		if (head == null || head.next == null) {
			return head;
		}

		// Split head into 'left' and 'right' sublists
		Node[] l_list = FrontBackSplit(head);
		Node left = l_list[0];
		Node right = l_list[1];

		// Recursively sort the sublists
		left = Merge_Sort(left);
		right = Merge_Sort(right);

		// merge the sorted sublists
		return Sorted_MergeSort(left, right);
	}
// function to print nodes of given linked list
	public static void printNode(Node head) {
		Node node_ptr = head;
		while (node_ptr != null)  {
			System.out.print(node_ptr.data + " -> ");
			node_ptr = node_ptr.next;
		}

		System.out.println("null");
	}

	public static void main(String[] args) {
		// input linked list
		int[] l_list = { 4,1,6,2,7,3,8 };
        
		Node head = null;
		for (int key: l_list) {
			head = new Node(key, head);
		}
		//print the original list
       		 System.out.println("Original Linked List: ");
        		printNode(head);
		// sort the list
		head = Merge_Sort(head);

		// print the sorted list
		System.out.println("\nSorted Linked List:");
		printNode(head);
	}
}

Output:

Original Linked List:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Sorted Linked List:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null

Sort ArrayList Using Merge Sort In Java

Like Arrays and Linked lists, we can also use this technique for sorting an ArrayList. We will use similar routines to divide the ArrayList recursively and then merge the sublists.

The below Java code implements the Merge sort technique for ArrayList.

import java.util.ArrayList;

class Main {
//splits arrayList into sub lists.
public static void merge_Sort(ArrayList<Integer> numList){
  int mid;
  ArrayList<Integer> left = new ArrayList<>();
  ArrayList<Integer> right = new ArrayList<>();
  
  if (numList.size() > 1) {
     mid = numList.size() / 2;
        // left sublist
        for (int i = 0; i < mid; i++) 
            left.add(numList.get(i));
 
        //right sublist
        for (int j = mid; j < numList.size(); j++)
            right.add(numList.get(j));
     //recursively call merge_Sort for left and right sublists        
     merge_Sort(left);
     merge_Sort(right);
     //now merge both arrays 
     merge(numList, left, right);
  }
}
private static void merge(ArrayList<Integer> numList, ArrayList<Integer> left, ArrayList<Integer> right){
  //temporary arraylist to build the merged list
  ArrayList<Integer> temp = new ArrayList<>(); 
  
  //initial indices for lists 
  int numbersIndex = 0;    
  int leftIndex = 0;
  int rightIndex = 0;
  //traverse left and righ lists for merging
  while (leftIndex < left.size() && rightIndex < right.size()) {
    if (left.get(leftIndex) < right.get(rightIndex) ) {
            numList.set(numbersIndex, left.get(leftIndex));
            leftIndex++;
        } else {
            numList.set(numbersIndex, right.get(rightIndex));
            rightIndex++;
        }
        numbersIndex++;
    }
    //copy remaining elements from both lists, if any.
    int tempIndex = 0;
    if (leftIndex >= left.size()) {
        temp = right;
        tempIndex = rightIndex;
    } 
    else {
        temp = left;
        tempIndex = leftIndex;
    }
 
    for (int i = tempIndex; i < temp.size(); i++) {
        numList.set(numbersIndex, temp.get(i));
        numbersIndex++;
    }
 }
public static void main(String[] args) {
    //declare an ArrayList
    ArrayList<Integer> numList = new ArrayList<>();
    int temp;
    //populate the ArrayList with random numbers
    for (int i = 1; i <= 9; i++)
      numList.add( (int)(Math.random() * 50 + 1) );
    //print original ArrayList of random numbers    
    System.out.println("Original ArrayList:");
    for(int val: numList)
      System.out.print(val + " ");
    //call merge_Sort routine 
    merge_Sort(numList);

    //print the sorted ArrayList
    System.out.println("\nSorted ArrayList:");
    for(int ele: numList)
      System.out.print(ele + " ");
    System.out.println();
  }
}

Output:

Original ArrayList:
17 40 36 7 6 23 35 2 38
Sorted ArrayList:
2 6 7 17 23 35 36 38 40

Frequently Asked Questions

Q #1) Can Merge sort be done without Recursion?

Answer: Yes. We can perform a non-recursive Merge sort called ‘iterative Merge sort’. This is a bottom-up approach that begins by merging sub-arrays with a single element into a sub-array of two elements.

Then these 2-element sub-arrays are merged into 4-element sub arrays and so on using iterative constructs. This process continues until we have a sorted array.

Q #2) Can Merge sort be done in place?

Answer: Merge sort generally is not in-place. But we can make it in-place by using some clever implementation. For example, by storing two elements value at one position. This can be extracted afterward using modulus and division.

Q #3) What is a 3 way Merge sort?

Answer: The technique we have seen above is a 2-way Merge sort wherein we split the array to be sorted into two parts. Then we sort and merge the array.

In a 3-way Merge sort, instead of splitting the array into 2 parts, we split it into 3 parts, then sort and finally merge it.

Q #4) What is the time complexity of Mergesort?

Answer: The overall time complexity of Merge sort in all cases is O (nlogn).

Q #5) Where is the Merge sort used?

Answer: It is mostly used in sorting the linked list in O (nlogn) time. It is also used in distributed scenarios wherein new data comes in the system before or post sorting. This is also used in various database scenarios.

Conclusion

Merge sort is a stable sort and is performed by first splitting the data set repeatedly into subsets and then sorting and merging these subsets to form a sorted data set. The data set is split until each data set is trivial and easy to sort.

We have seen the recursive and iterative approaches to the sorting technique. We have also discussed the sorting of Linked List and ArrayList data structure using Mergesort.

We will continue with the discussion of more sorting techniques in our upcoming tutorials. Stay Tuned!

=> Visit Here For The Exclusive Java Training Tutorial Series.