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.
Table of Contents:
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.