# Merge Sort in Java

This tutorial explains merge sort algorithm with example implementation in java. It starts off with explaining how merge sort uses divide-and-conquer technique. This is followed by a step-by-step walkthrough showing how recursive merge sort can be used to used for ordering a 5 number list. Next we will go through java implementation of merge sort followed by its detailed explanation.

Merge Sort is a divide-and-conquer algorithm
Merge Sort comes under the category of divide-and-conquer algorithms. Divide-and-conquer algorithms work on the principle of dividing the problem into smaller, more manageable, sub-problems recursively until these sub-problems become simple enough to be solved directly. The solutions to these sub-problems are then merged in the reverse order in the recursive chain to obtain the final desired result.

You can see a whiteboard animation video explanation of how merge sort works and get a code walk-through in this YouTube video

Step-by-step walkthrough of how merge sort works
We will take up merge sort solution in the most optimised way i.e. recursively. Lets say the list to be sorted is [10, 5, 100, 1,10000].

Stage 1- DIVIDE
Recursive Call Level 1
We divide the list into 2 sub-lists [10,5] and [100,1,10000]. We then pick the left sub-list [10,5] and see that the size of the list > 1 . Its important to note at this point that list size of 1 is the boundary condition for recursiveness i.e. the recursive calls stop at the boundary condition and the solved sub-problems are returned back as results of recursive calls. So, since size of list [10,5] is > 1 hence we again make a recursive call for merge sorting of the left sub-list.

Recursive Call Level 1.1
Sub-list [10,5] is now the candidate for merge sort so it is now divided into 2 halves  and . Now these two sub-lists are of size 1 which is the boundary condition as explained above. So these two sub-lists are assumed to be correctly merge sorted and returned. As they are returned they are merged in the correct order to produce the sorted sub-list [5,10].

Stage 2- CONQUER
This is the second stage of merge sort. During merging both of the sub-lists are read with individual pointers. The elements at the heads of the two sub-lists are compared and the lesser one is picked and pushed into a third list , called say the merged-list. The pointer for the sub-list from which the element was picked is moved forward to point to the next element.

Similarly, the right sub-list [100,1,10000] is merge sorted with multiple recursive calls to get [1,100,10000]  as the result.

The left and right sorted sub-lists are merged to get the final sorted list [1,5,10,100,10000].
Recursive Merge sort algorithm implemented in Java

Recursive Merge sort algorithm implemented in Java
```package com.javabrahman.algorithms.sorts;
public class MergeSort {
static int inputArray[] = { 10, 5, 100, 1,10000};

public static int[] doMergeSort(int[] values) {
if(values.length<=1){
return values;
}
int mid=(values.length)/2;
int[] left=new int[mid];
int[] right=new int[(values.length)-mid];
for(int leftCount=0;leftCount<mid;leftCount++){
left[leftCount]=values[leftCount];
}
for(int rightCount=0;rightCount<((values.length)-mid); rightCount++){
right[rightCount]=values[mid+rightCount];
}
return merge(doMergeSort(left),doMergeSort(right));
}

public static int[] merge(int[] left, int[]right){
int leftCounter=0,rightCounter=0, mergedCounter=0;
int merged[]=new int[left.length+right.length];
while(leftCounter < left.length && rightCounter < right.length){
if(left[leftCounter]<=right[rightCounter]){
merged[mergedCounter]=left[leftCounter];
leftCounter++;
mergedCounter++;
}else{
merged[mergedCounter]=right[rightCounter];
rightCounter++;
mergedCounter++;
}
}
while(leftCounter<left.length){
merged[mergedCounter]=left[leftCounter];
leftCounter++;
mergedCounter++;
}
while(rightCounter<right.length){
merged[mergedCounter]=right[rightCounter];
rightCounter++;
mergedCounter++;
}
return merged;
}

public static void printArray(int[] sortedArray) {
for (int i = 0; i < sortedArray.length; i++) {
System.out.print(" " + sortedArray[i]);
}
}

public static void main(String args[]) {
System.out.print("Array Before Sorting->");
printArray(inputArray);
int sortedArray[]=doMergeSort(inputArray);
System.out.print("\nArray After Sorting ->");
printArray(sortedArray);
}
}```
OUTPUT of the above code
Array Before Sorting-> 10 5 100 1 10000
Array After Sorting -> 1 5 10 100 10000
Explanation of the code

• The `doMergeSort()` method is responsible for merge sorting of a list of elements passed to it. It does the following –
• Divides the list passed to it into 2 lists – left and right.
• Recursively calls `doMergeSort()` on the left and right sub-lists
• It merges the left and right sub-lists by calling the `merge()` method
• The boundary condition for this method is `1`. I.e. if the size of the list being sorted by this method is `1` then the list is returned back as it is.
• The `merge()` method iterates over the two sub-lists left and right passed to it and merges them in the correct sorting order.
• Mechanism of merging – Merging of the sub-lists works as follows –
1. Both of the sub-lists are read with individual pointers.
2. The elements at the heads of the two sub-lists are compared and the lesser one is picked and pushed into a third list , called say the merged-list.
3. The pointer for the sub-list from which the element was picked is moved forward to point to the next element.
• The `main()` method orchestrates the sorting.
• The instance element `inputArray[]` holds the list to be sorted.

Summary
In this tutorial on merge sort algorithm in java we understood the sorting algorithm’s divide-and-conquer nature, understood the algorithm’s working by a step-by-step walkthrough of sorting of a 5-number list, saw the java code for implementing recursive merge sort and finally understood the java program’s working in detail. Copyright © 2014-2022 JavaBrahman.com, all rights reserved.