Skip to content

Instantly share code, notes, and snippets.

@cocodrips
Created July 5, 2013 21:27
Show Gist options
  • Save cocodrips/5937371 to your computer and use it in GitHub Desktop.
Save cocodrips/5937371 to your computer and use it in GitHub Desktop.
mergeSort in Java
void mergeSort(int[] array, int low, int high){
if(low < high){
int middle = (low + high) / 2;
mergeSort(array, low, middle);
mergeSort(array, middle+1, high);
merge(array, low, middle, high);
}
}
void merge(int[] array, int low, int middle, int high){
int[] helper = new int[array.length];
for (int i = low; i <= high; i++) {
helper[i] = array[i];
}
int helperLeft = low;
int helperRight = middle+1;
int current = low;
while (helperLeft <= middle && helperRight <=high) {
if(helper[helperLeft] <= helper[helperRight]){
array[current] = helper[helperLeft];
helperLeft++;
}else{
array[current] = helper[helperRight];
helperRight++;
}
current ++;
}
int remaining = middle - helperLeft;
for (int i = 0; i <= remaining; i++) {
array[current+i] = helper[helperLeft+ i];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment