Skip to content

Instantly share code, notes, and snippets.

@scientificRat
Created January 16, 2019 08:24
Show Gist options
  • Save scientificRat/c3b5ddfc2d1d33d7e1ddcb5b4327e30b to your computer and use it in GitHub Desktop.
Save scientificRat/c3b5ddfc2d1d33d7e1ddcb5b4327e30b to your computer and use it in GitHub Desktop.
merge_sort implementation in c++(no array copy)
void mergeSort(int *arr, int *out, int start, int end) {
if (end == start + 1) {
out[0] = arr[start];
return;
}
int mid = (start + end) / 2;
int left_length = mid - start;
int right_length = end - mid;
int *left = new int[left_length];
int *right = new int[right_length];
mergeSort(arr, left, start, mid);
mergeSort(arr, right, mid, end);
// merge
int i = 0;
int j = 0;
int k = 0;
while (i < left_length && j < right_length) {
if (left[i] <= right[j]) {
out[k] = left[i];
++i;
} else {
out[k] = right[j];
++j;
}
++k;
}
while (i < left_length) {
out[k] = left[i];
++i;
++k;
}
while (j < right_length) {
out[k] = right[j];
++j;
++k;
}
delete[] left;
delete[] right;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment