Created
August 11, 2019 18:25
-
-
Save RitamChakraborty/3c24f98d82bf5ff3e629ad9bc6c3983f to your computer and use it in GitHub Desktop.
Merge Sort algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class MergeSort { | |
private final int[] arr; | |
public MergeSort(int[] arr) { | |
this.arr = arr; | |
} | |
public int[] sort() { | |
int start = 0; | |
int end = arr.length - 1; | |
mergeSort(start, end); | |
return arr; | |
} | |
private void mergeSort(int start, int end) { | |
if (start < end) { // Return if start == end | |
int mid = (start + end) / 2; // Find the mid | |
mergeSort(start, mid); // Do recursion with left side variables | |
mergeSort(mid + 1, end); // Do recursion with right side variables | |
merge(start, mid, end); // When both of the recursion return the merge left and right variables | |
} | |
} | |
private void merge(int start, int mid, int end) { | |
int m = (mid - start) + 1; // Size of the first array | |
int n = (end - mid); | |
int[] arr1 = new int[m]; // Create the first array | |
int[] arr2 = new int[n]; // Create the second array | |
int i, j, k = start; | |
// Copy m number of variables starting from main array starting from index start to first array | |
for (i = 0; i < m; i++) { | |
arr1[i] = arr[k++]; | |
} | |
// Copy n number of variables starting from main array staring from mid + 1 to the second array | |
for (j = 0; j < n; j++) { | |
arr2[j] = arr[k++]; | |
} | |
i = j = 0; | |
k = start; | |
// Break through the while when either i become m or j becomes n | |
while (i != m && j != n) { | |
/* | |
Basically it's just one kinda sort | |
- if element from the first array is less than the element from the second array then that element should be inserted in the main array | |
- otherwise element from the second array should be entered to the main array | |
*/ | |
if (arr1[i] < arr2[j]) { | |
arr[k++] = arr1[i++]; | |
} else { | |
arr[k++] = arr2[j++]; | |
} | |
} | |
// If any elements remaining in the first array then those should also be inserted in the main array | |
while (i != m) { | |
arr[k++] = arr1[i++]; | |
} | |
// If any elements remaining in the second array then those should also be inserted in the main array | |
while (j != n) { | |
arr[k++] = arr2[j++]; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment