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 [10] and [5]. 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

Explanation of the code

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

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 [10] and [5]. 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

```
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

- 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 -- 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.

- The
`main()`

method orchestrates the sorting. - The instance element
`inputArray[]`

holds the list to be sorted.