This tutorial shows how to write Merge sort program in Java. Merge sort is termed as a "divide and conquer algorithm" and it is considered to be more efficient than the simple sort algorithms like selection sort and insertion sort.
Merge sort algorithm
The algorithm for merge sort is based on the process of merging where two sorted arrays are merged to form a large sorted array. To merge the smaller arrays first you do need to divide your array into smaller arrays too so effectively Merge sort is a two step process.
- Divide the input array into two halves this process is carried out recursively until you get sub-arrays with only one element which is the base case for the recursive division. These sub-arrays of one element each are considered as sorted arrays.
- In this step these smaller arrays are sorted and merged recursively until you again get the larger sorted array. Merging process starts from bottom where a pair of single element sub-arrays are sorted and merged to create an array of two elements. Then a pair of such sorted sub-arrays of two elements are merged to create a sorted array of four elements and so on.
Following image shows the sub-division process for an array {43, 39, 54, 61, 81, 55, 92, 7}
At this point base case is encountered which starts the merging process that is explained using the following image.
Merge Sort Java program
public class MergeSort {
public static void main(String[] args) {
int[] arr = {43, 39, 54, 61, 81, 55, 92, 7, 0, 15, 112, 10};
System.out.println("Original array- " + Arrays.toString(arr));
MergeSort ms = new MergeSort();
ms.mergeSortRecursive(arr, 0, arr.length-1);
System.out.println("Sorted array after merge sorting- " + Arrays.toString(arr));
}
private void mergeSortRecursive(int[] arr, int start, int end){
//base case
if (start == end){
return;
}else{
// Middle point of the array
int middle = (start + end)/2;
// divide array into two parts using middle point
mergeSortRecursive(arr, start, middle);
mergeSortRecursive(arr, middle+1, end);
// call merge process
merge(arr, start, middle, end);
}
}
private void merge(int[] arr, int start, int middle, int end){
// Create two temp arrays for two halves
int temArray1Length = middle - start + 1;
int temArray2Length = end - middle;
int[] temp1 = new int[temArray1Length];
int[] temp2 = new int[temArray2Length];
for(int i = 0; i < temArray1Length; i++){
temp1[i] = arr[start + i];
}
for(int j = 0; j < temArray2Length; j++){
temp2[j] = arr[middle + 1 + j];
}
int i =0;
int j = 0;
// merging process, merge two temp arrays put the
// sorted elements in original array
while((i < temArray1Length) && (j < temArray2Length)){
if(temp1[i] < temp2[j]){
arr[start] = temp1[i++];
}else{
arr[start] = temp2[j++];
}
start++;
}
// Add left over elements from temp arrays
while(i < temArray1Length){
arr[start++] = temp1[i++];
}
while(j < temArray2Length){
arr[start++] = temp2[j++];
}
}
}
Output
Original array- [43, 39, 54, 61, 81, 55, 92, 7, 0, 15, 112, 10] Sorted array after merge sorting- [0, 7, 10, 15, 39, 43, 54, 55, 61, 81, 92, 112]
Merge sort time and space complexity
Time complexity of merge sort is O(n*logn) where logn is the complexity of sub-dividing the array and n is the complexity for merging n elements at each level.
Space complexity of merge sort is O(n) as extra space for temp array is required which is equal to the length of the input array.
That's all for the topic Merge sort Java Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment