Merge sort with raw C++ array

Question

Merge function:

void merge(int outputArray[], int firstArray[], int sizeFirst, int secondArray[], int sizeSecond){
    int p = 0;
    int p1 = 0; 
    int p2 = 0;
    while(p1 < sizeFirst && p2 < sizeSecond){
        if(first[p1] < second[p2])
            outputArray[p++] = firstArray[p1++];
        else 
            outputArray[p++] = secondArray[p2++];
    }

    while(p1 < sizeFirst) outputArray[p++] = firstArray[p1++];
    while(p2 < sizeSecond) outputArray[p++] = secondArray[p2++];
}

Sort function:

void sort(int numbers[], int size){
    if(size == 1) return;
    int mid = size/2;
    int firstPartSize = mid;
    int secondPartSize = size - mid;

    int firstArray[firstPartSize];
    int secondArray[secondPartSize];

    for(int i = 0 ; i < size ;i++){
        if(i < mid)
            firstArray[i] = numbers[i];
        else 
            secondArray[i - mid] = numbers[i];
    }

    sort(firstArray, firstPartSize);
    sort(secondArray, secondPartSize);
    merge(numbers, first, firstPartSize, second, secondPartSize);
}

Personally I think the number of arguments in the merge function are bit too many. I considered making a different function that calculates size of the array but that didn't seem to work with my current knowledge of the language.

1. Should I care about readability in standard algorithms?
2. What other names would you suggest instead of p, p1, p2 so that readability is not hampered?
3. Are there any other bugs or problems with the code?

Answer 1

With regards to variable names and readability, I would recommend the following:

• Change p to outputIndex

• Change p1 to firstIndex

• Change p2 to secondIndex

• Change sizeFirst to firstSize

• Change sizeSecond to secondSize

Answer 2

• The most important property of a merge sort is stability: elements comparing equal maintain the original order. A condition

  if(first[p1] < second[p2])
  

  destabilizes the algorithm. It shall read

  if(first[p1] <= second[p2])
  

• Replace the final while loops with std::copy.

• Split the copy loop into two:

  for (int i = 0 ; i < mid ;i++) {
      firstArray[i] = numbers[i];
  }
  
  for (int i = mid ; i < size ;i++) {
      secondArray[i - mid] = numbers[i];
  }
  

  Then replace them with two calls to std::copy.

Answer 3

C++ does not allow run time array sizing in the standard language:

int firstArray[firstPartSize];
int secondArray[secondPartSize];

Though it is provided as an extension in some compilers.
But you should really use std::vector here.

std::vector<int> firstArray(firstPartSize);
std::vector<int> secondArray(secondPartSize);

I am not sure if this has been updated in the later language extensions (C++11/C++14 would be grateful if somebody could comment with standard info).

The other thing about your solution is that it uses \$O(n^2)\$ space. This algorithm can be done in \$O(n)\$ space. So there is some work to be done there.