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
[su_box title="Recursive Merge sort algorithm implemented in Java" style="soft" box_color="#fcba43" title_color="#00000" radius="4" Class="for-shortcodebox"][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);
}
}[/java][/su_box]
OUTPUT of the above code[su_note note_color="#1a1a1a" text_color="#DAD9D7"] Array Before Sorting-> 10 5 100 1 10000
Array After Sorting -> 1 5 10 100 10000[/su_note]
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 is1then 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.
Sorting Algorithm Tutorials on JavaBrahman
Bubble SortClick to Read Bubble Sort Tutorial Insertion SortClick to Read Insertion Sort Tutorial Selection SortClick to Read Selection Sort Tutorial Merge SortClick to Read Merge Sort Tutorial Radix SortClick to Read Radix Sort Tutorial
[/su_note]