Merge Sort in Java
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
public class MergeSortExample
{
// method that implements merge sort
static void mergeSort(int a[], int i, int j)
{
// find the middle point
int mid = (j + i) / 2;
if(j > i)
{
// recursively splitting the array into two halves
mergeSort(a, i, mid); // first half
mergeSort(a, mid + 1, j); // second half
// merging the two halves to
// form a bigger array
merger(a, i, mid, mid + 1, j);
}
}
// The merger() method merges the two sorted array
// The first sorted array starts from the index s1 and ends at e1
// Similarly, the second sorted array starts from the index s2 and ends at e2
static void merger(int arr[], int s1, int e1, int s2, int e2)
{
// calculating the temp array
int length = e2 - s1 + 1;
// the temp array
int temp[] = new int[length];
// two pointers pointes to the starting
// index of the two sorted arrays
int ptr1 = s1, ptr2 = s2;
// index is the variable used to
// iterate over the temp array
int index = 0;
// while loop does the actual merging and
// stores the resultant sorted array in temp
while(ptr1 <= e1 && ptr2 <= e2)
{
if(ptr1 <= e1 && (arr[ptr1] < arr[ptr2]))
{
temp[index] = arr[ptr1];
ptr1 = ptr1 + 1;
}
else if(ptr2 <= e2)
{
temp[index] = arr[ptr2];
ptr2 = ptr2 + 1;
}
index = index + 1;
}
// copying remaining elements of the arr to temp
while(ptr1 <= e1)
{
temp[index] = arr[ptr1];
ptr1 = ptr1 + 1;
index = index + 1;
}
// copying remaining elements of the arr to temp
while(ptr2 <= e2)
{
temp[index] = arr[ptr2];
ptr2 = ptr2 + 1;
index = index + 1;
}
// resetting the index to 0
index = 0;
// copying the values of temp array
// in the array arr
for(int i = s1; i <= e2; i++)
{
arr[i] = temp[index];
index = index + 1;
}
}
// main method
public static void main(String argvs[])
{
// given input array
int a[] = {67, 78, 34, 12, 30, 6, 9, 21};
// calculating size of the array
int size = a.length;
System.out.println("The array before sorting is: ");
for(int i = 0; i < size; i++)
{
System.out.print(a[i] + " ");
}
System.out.println("\n");
// invoking method mergeSort()
mergeSort(a, 0, size - 1);
System.out.println("The array after sorting is: ");
// displaying the sorted array
for(int i = 0; i < size; i++)
{
System.out.print(a[i] + " ");
}
}
}
Output:
The array before sorting is: 67 78 34 12 30 6 9 21 The array after sorting is: 6 9 12 21 30 34 67 78
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.