Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Java code for Merge Sort
import java.util.*;
public class MergeSort {
public static void main(String[] args) {
// get array and call mergeSort() on it
mergeSort(array);
}
public static void mergeSort(int[] array) {
int n = array.length;
if (n < 2) // base case, down to one element
return;
int mid = n/2;
int[] left = new int[mid];
int[] right = new int[n - mid];
for (int i = 0; i < mid; i++) {
left[i] = array[i];
}
for (int j = mid; j < n; j++) {
right[j - mid] = array[j];
}
mergeSort(left);
mergeSort(right);
merge(left, right, array);
}
public static void merge(int[] L, int[] R, int[] A) {
int nL = L.length;
int nR = R.length;
int i = 0;
int j = 0;
int k = 0;
while (i < nL && j < nR) {
if (L[i] <= R[j]) {
A[k] = L[i];
i++;
} else {
A[k] = R[j];
j++;
}
k++;
}
/* Left array isn't empty */
while (i < nL) {
A[k] = L[i];
i++;
k++;
}
/* Right array isn't empty */
while (j < nR) {
A[k] = R[j];
j++;
k++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.