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
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
- The boundary condition for this method is
1. I.e. if the size of the list being sorted by this method is
1then the list is returned back as it is.
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.
main()method orchestrates the sorting.
- The instance element
inputArrayholds the list to be sorted.
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.