Skip to content

Instantly share code, notes, and snippets.

@LionRoar
Created October 2, 2017 18:16
Show Gist options
  • Save LionRoar/cb9e1d6dcfa3596f318d6a3e9886f9ec to your computer and use it in GitHub Desktop.
Save LionRoar/cb9e1d6dcfa3596f318d6a3e9886f9ec to your computer and use it in GitHub Desktop.
Merge Sort in C++
#include "mergeSort.h"
mergeSort::mergeSort(){}
mergeSort::~mergeSort(){}
void mergeSort::MergeSort(int a[], int n) {
MergeSort(a, 0, n-1);
}
void mergeSort::MergeSort(int a[], int low, int high) {
if (low >= high)return;
else {
int mid = (low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid + 1, high);
Merge(a, low, mid, mid + 1, high);
}
}
void mergeSort::Merge(int a[], int left_low, int left_high, int right_low, int right_high) {
int len = right_high - left_low + 1;
int *tmp = new int[len];
int left = left_low;
int right = right_low;
for (int i = 0; i < len;i++) {
if (left > left_high) {tmp[i] = a[right++];}
else if (right > right_high) { tmp[i] = a[left++]; }
else if (a[left] <= a[right]) { tmp[i] = a[left++]; }
else { tmp[i] = a[right++]; }
}
for (int i = 0; i < len;i++) { a[left_low++] = tmp[i]; }
delete tmp;
}
class mergeSort
{
public:
mergeSort();
~mergeSort();
void MergeSort(int a[], int n);
private :
void MergeSort(int a[], int low, int high);
void Merge(int a[], int left_low, int left_high, int right_low, int right_high);
};
@m0rphed
Copy link

m0rphed commented Dec 14, 2018

Good example, thanks!
I think this: delete tmp; should be more like this: delete[] tmp;

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment