How does it look? Comments, code correctness, etc.

//Function Prototypes
void buildArray(int anArray[]);

void printArray(int anArray[], int start, int end);
void sortArray(int start, int end, int masterArray[], int tempArray[]);
void mergeArray(int start, int split, int end, int masterArray[], int tempArray[]);

void bruteCount(int masterArray[]);

//Globals BAD, but gets the job done here
long long INVERSIONS_SORT = 0;
long long INVERSIONS_BRUTE = 0;
const int size = 100000;


void main() {
  int masterArray[size];
  int tempArray[size];

  buildArray(masterArray);

  bruteCount(masterArray);
  cout << "Inversion from Brute: " << INVERSIONS_BRUTE << endl;
  cin.get();

  sortArray(0, size - 1, masterArray, tempArray);
  cout << "Inversions from Sort: " << INVERSIONS_SORT << endl;

  cin.get();
}

//Builds an array from a txt file
void buildArray(int anArray[]) {
  ifstream dataFile;
  dataFile.open("integerArray.txt", ios::in);

  for (int i = 0; i < size; i++)
    dataFile >> anArray[i];
}

//Prints the entire array
void printArray(int anArray[], int start, int end) {
  for (int i = start; i <= end; i++)
    cout << anArray[i] << " ";

  cout << endl;
}

//Recursive function to split the array into sub arrays for merging
void sortArray(int start, int end, int masterArray[], int tempArray[]) {
  int split = (start + end) / 2;

  if (start < end) {
    sortArray(start, split, masterArray, tempArray);
    sortArray(split + 1, end, masterArray, tempArray);
    mergeArray(start, split, end, masterArray, tempArray);
  }


}

//Master function to marge two arrays into the correct order, and track the number of inversions
void mergeArray(int start, int split, int end, int masterArray[], int tempArray[]) {
  int leftCount = start; //Counter for left array
  int rightCount = split+1; //Counter for right array
  int tempCount = start; //Counter for temporary array

  while ((leftCount <= split) && (rightCount <= end)) { //When there are still values in both arrays
    if (masterArray[leftCount] <= masterArray[rightCount]) { //If value of left array is lower
      tempArray[tempCount] = masterArray[leftCount];
      leftCount++;
    }
    else {
      tempArray[tempCount] = masterArray[rightCount];  //If value of right array is lower
      INVERSIONS_SORT = INVERSIONS_SORT + (split + 1 - leftCount);  //If value of the right array is lower, add how many left array values are higher (number of inversions) and add to count
      rightCount++;
    }
    tempCount++;
  }

  //Cleanup when either array is done
  if (leftCount > split) {
    for (int i = rightCount; i <= end; i++) {
      tempArray[tempCount] = masterArray[i];
      tempCount++;
    }
  }
  else {
    for (int i = leftCount; i <= split; i++) {
      tempArray[tempCount] = masterArray[i];
      tempCount++;
    }
  }

  //Copy back into master array
  for (int i = start; i <= end; i++)
    masterArray[i] = tempArray[i];

}


//Counts the number of inversions via brute force, here to check to see if MergeSort method is working correctly
void bruteCount(int masterArray[]) {
  int i, j;

  for (i = 0; i < size-1; i++)
    for (j = i + 1; j < size; j++)
      if (masterArray[i] > masterArray[j])
        INVERSIONS_BRUTE++; 
}
  • The comment about the globals is noisy, but at least you're aware that they're bad. You can reduce the possibility of bugs by removing them, which is always good idea. Otherwise, it could suggest that this implementation needs reworking, especially if you do encounter some bugs.

    Side-note: size is technically a constant, not a global. It's okay to have constants in global scope as they cannot be modified elsewhere.

  • I would recommend replacing the C-arrays with a storage container such as std::vector or std::array (if you have C++11). In C++, it's not good to pass C-arrays to functions because they decay to pointers instead of passing the array itself. Storage containers, on the other hand, do not do this; they pass an object. That said, your implementation looks very C-like, although that's not relevant to the sorting. It's still worth knowing about storage containers in C++.

    You will also be able to invoke operator= in one line to reassign the master array to the temp array instead of using a manual loop. These little things will help make your code cleaner.

  • For bruteCount():

    • Why are i and j declared outside the loop statement? It's done differently elsewhere, so it should be done here as well.
    • The loops and the if statement should have curly braces, even if the body of a statement is just one line (also more a general recommendation). Not having them this way could hurt maintenance, in case you ever need to add or remove something.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.