Merge Sort in Java
The merge sort is a divide and conquer algorithm that divides the input array into equal subarrays and then merges back those subarrays into a sorted array. The process of merge sort is to divide the array into two equal subarrays, sort each subarray, and then merge the sorted subarrays back together. This process is repeated until the entire array is sorted.
Divide and Conquer Algorithm :
In Divide and Conquer technique,
1) Divide : a problem is divided into subproblems.
2) Conquer : When the solution to each subproblem is reached,
3) Combine : we then ‘combine’ the results from the solution of the subproblems to solve the main problem.
So, In Divide and Conquer technique, a problem is divided into subproblems. When the solution to each subproblem is reached, we then ‘combine‘ the results from the solution of the subproblems to solve the main problem.
Array : [A, B, C, D, E, F]
Suppose we had to sort an array Arr which is our problem. We divide this problem into subproblem and sort a sub-section of this array starting at index a and ending at index f, denoted as Arr[a..f].
Divide :
If c is the half-way point between a and f, then we can split the subarray Arr[a..f] into two arrays Arr[a..c] and Arr[c+1, f].
Conquer :
In the conquer step, we try to sort both the subarrays Arr[a..c] and Arr[c+1, f]. If we haven’t yet reached the base case, we again divide both these subarrays and try to sort them.
Combine :
When the conquer step reaches the base step and we get two sorted subarrays Arr[a..c] and Arr[c+1, f] for array Arr[a..f], we now combine the results to create a sorted array Arr[a..f] from two sorted subarrays Arr[a..c] and Arr[c+1, f].
MergeSort Algorithm Syntax :
MergeSort(Arr, a, f):
if a > f
return
c = (a+f)/2 // Divide
mergeSort(Arr, a, c) // Conquer
mergeSort(Arr, c+1, f) // Conquer
merge(Arr, a, c, f) // CombineTo sort an entire array, we need to call MergeSort(Arr, 0, length(A)-1).
Merge Sort Complexity
Time Complexity
Best : O(n*log n)
When the array is already sorted or nearly sorted.
Worst : O(n*log n)
When the array is randomly ordered.
Average : O(n*log n)
When the array is sorted in reverse order.
Space Complexity : O(n)
As an additional space is required for the temporary array used during merging, space complexity of merge sort is O(n)
Stability : Yes
Advantages of Merge Sort:
1) Merge sort is a stable sorting algorithm, which means it maintains the relative order of equal elements in the input array.
2) Merge sort has a worst-case time complexity of O(n*log n) , which means it performs well even on large dataset.
3) Merge Sort works on divide-and-conquer approach which is straightforward.
4) Since we can independently merge subarrays merge sort makes itself suitable for parallel processing.
Disadvantages of Merge Sort:
1) Merge sort requires additional memory to store the merged sub-arrays during the sorting process.
2) Merge sort is not an in-place sorting algorithm, which means it requires additional memory to store the sorted data. This can be a disadvantage in applications where memory usage is a concern.
3) Merge Sort is slower than QuickSort in general. QuickSort is more cache friendly because it works in-place.
Applications of Merge Sort:
1) Merge Sort is used sorting large datasets
2) Merge Sort is used for external sorting when the dataset is too large to fit in memory
3) Merge Sort is useful in inversion counting
4) Merge Sort and its variations are widely used in library methods of programming languages. Its variation TimSort is used in Python, Java Android and Swift.Arrays.sort in Java uses QuickSort while Collections.sort uses MergeSort.
5) Merge Sort is considered as a preferred algorithm for sorting Linked lists.
6) Merge Sort can easily be used for parallel processing as we can independently sort subarrays and then merge.
7) The merge function of merge sort can efficiently solve the problems like union and intersection of two sorted arrays.
Program 1 : Merge Sort in Java
public class MergeSortProg {
void merge(int arr[], int start, int mid, int end) {
int n1 = mid - start + 1;
int n2 = end - mid;
int LeftArray[] = new int[n1];
int RightArray[] = new int[n2];
for (int i = 0; i < n1; i++) LeftArray[i] = arr[start + i];
for (int j = 0; j < n2; j++) RightArray[j] = arr[mid + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = start;
while (i < n1 && j < n2) {
if (LeftArray[i] <= RightArray[j]) {
arr[k] = LeftArray[i];
i++;
} else {
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = LeftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = RightArray[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // Divide
mergeSort(arr, left, mid); // Conquer
mergeSort(arr, mid + 1, right); // Conquer
merge(arr, left, mid, right); // Combine
}
}
public static void main(String args[]) {
int arr[] = { 8, 16, 45, 34, 21, 14 };
System.out.println("Unsorted Array");
for (int val : arr) {
System.out.print(val + " ");
}
MergeSortProg merge_obj = new MergeSortProg();
merge_obj.mergeSort(arr, 0, arr.length - 1);
System.out.println("\n\n" + "Sorted Array in Ascending Order: ");
for (int val : arr) {
System.out.print(val + " ");
}
}
}Output :
Unsorted Array
8 16 45 34 21 14
Sorted Array in Ascending Order:
8 14 16 21 34 45 Program 2 : Merge Sort in Java
public class MergeSortProgram2 {
private static void mergeSort(int[] array) {
int length = array.length;
if (length <= 1) return; //base case
int middle = length / 2;
int[] leftArray = new int[middle];
int[] rightArray = new int[length - middle];
int i = 0; //left array
int j = 0; //right array
for(; i < length; i++) {
if(i < middle) {
leftArray[i] = array[i];
}
else {
rightArray[j] = array[i];
j++;
}
}
mergeSort(leftArray);
mergeSort(rightArray);
merge(leftArray, rightArray, array);
}
private static void merge(int[] leftArray, int[] rightArray, int[] array) {
int leftSize = array.length / 2;
int rightSize = array.length - leftSize;
int i = 0, l = 0, r = 0; //indices
//check the conditions for merging
while(l < leftSize && r < rightSize) {
if(leftArray[l] < rightArray[r]) {
array[i] = leftArray[l];
i++;
l++;
}
else {
array[i] = rightArray[r];
i++;
r++;
}
}
while(l < leftSize) {
array[i] = leftArray[l];
i++;
l++;
}
while(r < rightSize) {
array[i] = rightArray[r];
i++;
r++;
}
}
public static void main(String args[]) {
int arr[] = { 8, 16, 45, 34, 21, 14 };
System.out.println("Unsorted Array");
for (int val : arr) {
System.out.print(val + " ");
}
MergeSortProgram2 merge_obj = new MergeSortProgram2();
merge_obj.mergeSort(arr);
System.out.println("\n\n" + "Sorted Array in Ascending Order: ");
for (int val : arr) {
System.out.print(val + " ");
}
}
}Output :
Unsorted Array
8 16 45 34 21 14
Sorted Array in Ascending Order:
8 14 16 21 34 45