Skip to content

Instantly share code, notes, and snippets.

/.java Secret

Created February 21, 2018 17:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anonymous/9b88d3b603b0f1a597caffa01059b90b to your computer and use it in GitHub Desktop.
Save anonymous/9b88d3b603b0f1a597caffa01059b90b to your computer and use it in GitHub Desktop.
private static void mergeSort(int[] arr) {
int[] temp = new int[arr.length];
merge(arr, temp, 0, arr.length - 1);
}
private static void merge(int[] arr, int[] temp, int start, int end) {
if (start >= end) {
return;
}
int middle = (start + end) / 2;
merge(arr, temp, start, middle);
merge(arr, temp, middle + 1, end);
helper(arr, temp, start, middle, middle + 1, end);
}
private static void helper(int[] arr, int[] temp, int leftStart, int leftEnd, int rightStart, int rightEnd) {
int i = leftStart;
int j = rightStart;
int k = leftStart;
while (i <= leftEnd && j <= rightEnd) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
mergeCounter++;
}
else {
temp[k++] = arr[j++];
}
}
while (i <= leftEnd) {
temp[k++] = arr[i++];
}
while (j <= rightEnd) {
temp[k++] = arr[j++];
}
for (i = leftStart; i <= rightEnd; i++) {
arr[i] = temp[i];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment