I have my part of the MergeSort code done but there are some comparison and swapping problems. My temp vector that I have set up is copying the vector to be sorted into my temp vector the same way. For example my vector to be sorted would be v={5104, 8199, 123, 5678, 9999, 4356} and then at the end of the program the temp vector is set up the same way temp={5104, 8199, 123, 5678, 9999, 4356}. I have all the variables needed and I was told that there should be no for loops in the outplaceMerge method, only while and if/else statements. I wasn't going to post this question but I'm at a loss.

int main (int argc, char* argv[]) {
  //I have a method that makes the vector size its not shown 
  size_t n = vectorSize();
  vector<int> vect(n);

  std::random_device sd;
  std::mt19937 mt(sd());
  std::uniform_int_distribution<int> dist (0, 9999);

  for (size_t i = 0; i < n; ++i)
  {
      vect[i] = dist(mt);
  }
  mergeSort(vect);
  cout << "Merge time: " << ms << endl;
  vector<int> ACopy(vect);

  std::sort(ACopy.begin(), ACopy.end());
  if(vect == ACopy) {    
    cout << "Merge ok?     true" << endl;
  }else{
    cout << "Merge ok?      false" << endl;   
  }
  return EXIT_SUCCESS; 
}
/************************************************************/

size_t mergeSortH(vector<int>& v, vector<int>& temp, size_t first, size_t last) {   
    if (last - first > 1) {
        size_t mid = first+(last-first) / 2;
        mergeSortH(v, temp, first, mid);
        mergeSortH(v, temp, mid, last);
        outplaceMerge(v, temp, first, mid, last);
    }
//will return numCompares I just am waiting till I fix my sort
    return 0; 
}

/************************************************************/

size_t outplaceMerge(vector<int>& v, vector<int>& temp, size_t first, size_t mid, size_t last) {
  size_t numCompares = 0;
  size_t i1 = first;
  size_t i2 = mid;
  size_t i3 = first;

  while((v[first] < mid) && (v[first] < last)) {      
    if(v[first] < v[mid]) {
      temp[i3] = v[i1];
      ++i1;
    } else {
      temp[i3] = v[i2];
      ++i2;
    }    
    ++i3;
  }

  if(i1 > mid) {    
    while(i2 < last) {
      temp[i3] = v[i2];
      ++i2;
      ++i3;
    }   
  } else {
    while(i1 <= mid){
      temp[i3] = v[i1];
      ++i1;
      ++i3;    
    }
  }     
  cout << i3 << endl;  

  return numCompares;
}   
/************************************************************/

size_t mergeSort(vector<int>& v)
{
  vector<int> temp(v.size());
  return mergeSortH(v, temp, 0, v.size());
}

/************************************************************/

The vector should be sorted v={5104, 8199, 123, 5678, 9999, 4356} to temp={123, 4356, 5104, 5678, 8199, 9999} and the put those variables back into the original vector v={123, 4356, 5104, 5678, 8199, 9999}. There is no output needed it just has to be sorted, and the random number gen makes the original vector, so those values are just an example. The Acopy statement is compared to the merge sort after its completed to show whether or not its sorted. If the merge is = to Acopy then its returned true.

0 Answers