Select Page

Merge Sort in Java

Merge sort in Java uses the divide and conquer approach to sort the given array/ list. There are three steps involved in the merge sort.

1) Divide the given array into two halves (smaller arrays). Divides those two halves into further halves and continue to do so until further division is not possible.

2) Now, do the conquer by sorting the smaller arrays recursively.

3) Concatenate the smaller arrays that are sorted and it forms the bigger arrays. The concatenation of bigger arrays leads to an even bigger array, ultimately leading to a final array that is also sorted. Its size will be equal to the original array.

Algorithm and Pseudo Code

mergeSort(A[], i,  j)

If j > i

1. Get the mid-point to split the given array into two halves:

middle mid = i + (j – i) / 2

2. Invoke the mergeSort() method for the first half:

Call mergeSort(A, i, mid)

3. Similarly, invoke the mergeSort() for the second half:

Call mergeSort(A, mid + 1, j)

4. Combine the two sorted halves found in step 2 and 3:

Call merger(A, i, mid, mid + 1, r)

Java Program

The following Java program implements Merge sort.

FileName: MergeSortExample.java

Output:

Explanation: First, we split the input array into smaller arrays called sub-arrays. Perform the step until each sub-array has 1 element. Since, an array of a single element is always sorted, the merger() method is called to combine the smallest sub-arrays to  get a small sub-array, which is sorted, contains 2 elements. Now, two sub-arrays of length 2 are merged to get a sorted array of size 4. Again, two sub-arrays of size 4 are merged to get a sorted array of size 8. The array we get is a final sorted array. The merging of the two sorted arrays is done using the two-pointer approach. The first while loop present in the merger() method does the same. The following diagram depicts the same.

Analysis of Merge Sort

Merge sort is a stable algorithm. One of the main properties of the marge sort algorithm is that it does not depend on the arrangement of elements. The property is good as well as bad. For example, consider an array a[] = {67, 78, 80, 90}. We see that the array is already sorted. However, if we apply merge sort on this array, the merge sort does not care whether the array is sorted or not, i.e., it splits the array, which is already sorted, recursively and applies the conquer and combine approach. It is the cons of the merge sort algorithm.

The positive aspect is if we consider the array as a[] = {78, 67, 90, 80}, the divide and conquer approach comes very handy. For this type of inputs, merge sort emerges as one of the finest sorting algorithms.

Time Complexity

The time complexity of the merge sort is O(nlog(n)), where n is the number of elements present in the array or list. Since merge sort is independent of the arrangement of elements; therefore, the best, as well as the worst complexity, is O(nlog(n)).

Space Complexity

The space complexity of the merge sort algorithm is O(n), where n is the number of elements present in the array or list. It is due to the auxiliary array (temp array in our case) that is used for copying the elements from one array to another.

Conclusion

For arrays whose elements are almost sorted or sorted completely, merge sort is not the best sorting algorithm to go with. However, merge sort must be used for those arrays whose elements are jumbled a lot.