merge

void (int* arr, int n){
  MergeSort(arr, 0, n - 1);
}

void (int* arr, int low, int high){
  if(low < high){
  	int mid = low + (high - low) / 2;
  	MergeSort(arr, low, mid);
  	MergeSort(arr, mid + 1, high);
  	Merge(arr, low, mid + 1, high);
  }
}

void Merge(int* arr, int left_pos, int right_pos, int right_end) {
  int left_end = right_pos - 1;
  int tmp_pos = 0;
  int num_elements = right_end - left_pos + 1;
  int* _arr = new int[num_elements];
  while (left_pos <= left_end && right_pos <= right_end) {
    if (arr[left_pos] <= arr[right_pos]) {
      _arr[tmp_pos++] = move(arr[left_pos++]);
    } else {
      _arr[tmp_pos++] = move(arr[right_pos++]);
    }
  }
  while (left_pos <= left_end) {
    _arr[tmp_pos++] = move(arr[left_pos++]);
  }
  while (right_pos <= right_end) {
    _arr[tmp_pos++] = move(arr[right_pos++]);
  }
  for (int i = 0; i < num_elements; ++i, --right_end) {
    arr[right_end] = move(_arr[num_elements - i - 1]);
  }
  delete[] _arr;
}