Skip to content

Instantly share code, notes, and snippets.

@shahzadaazam
Last active October 27, 2020 06:00
Show Gist options
  • Save shahzadaazam/04ffbfc5506860b54b3a79ae253ad370 to your computer and use it in GitHub Desktop.
Save shahzadaazam/04ffbfc5506860b54b3a79ae253ad370 to your computer and use it in GitHub Desktop.
Mergesort recursive algorithm
public class MergeSort {
public static void main (String args[]) {
int[] arr = new int[]{5, 2, 3, 1, 4};
int[] helperArr = new int[arr.length];
mergeSort(arr, helperArr, 0, arr.length-1);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void mergeSort(int[] arr, int[] helperArr, int start, int end) {
// base case
if (start >= end) return;
int mid = (start + end) / 2;
// sort first half
mergeSort(arr, helperArr, start, mid);
// sort second half
mergeSort(arr, helperArr, mid + 1, end);
// combine both halves together
merge(arr, helperArr, start, mid, mid + 1, end);
}
public static void merge(int[] arr, int[] helperArr, int firstStart, int firstEnd, int lastStart, int lastEnd) {
int firstPtr = firstStart;
int lastPtr = lastStart;
int index = firstPtr;
for (int i = firstPtr; i <= lastEnd; i++) {
helperArr[i] = arr[i];
}
while (firstPtr <= firstEnd || lastPtr <= lastEnd) {
if (firstPtr <= firstEnd && lastPtr <= lastEnd) {
if (helperArr[firstPtr] <= helperArr[lastPtr]) {
arr[index] = helperArr[firstPtr];
index++;
firstPtr++;
} else {
arr[index] = helperArr[lastPtr];
index++;
lastPtr++;
}
} else if (firstPtr <= firstEnd) {
arr[index] = helperArr[firstPtr];
index++;
firstPtr++;
} else {
arr[index] = helperArr[lastPtr];
index++;
lastPtr++;
}
}
}
}
//reference: https://www.geeksforgeeks.org/merge-sort/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment