# Merge sort with raw C++ array

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.

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?

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

• Thanks! could you elaborate more on the last two variable names? – Nash Vail Dec 29 '14 at 14:07
• @nashmaniac: I just figured that you might as well use "first" and "second" as prefix in all variable names (and not as prefix in some of them and as posfix in others). – barak manos Dec 29 '14 at 14:10
• Yes, that makes sense. Thanks for the input. – Nash Vail Dec 29 '14 at 14:12
• @nashmaniac: You're welcome :) – barak manos Dec 29 '14 at 14:13
• 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.

• I thought of that, then figured that the else clause takes care of the "=" case. Am I missing something? Initially I had two separate for loops but then merged them into one for brevity. Was that a wrong decision? Why? I wasn't aware of std:: copy, thanks for mentioning, that is something to learn. – Nash Vail Dec 29 '14 at 18:38
• I think I misinterpreted the splitting part. Please ignore latter part of the comment above. – Nash Vail Dec 29 '14 at 18:40
• The else clause takes wrong care: according to your code, of two equal elements, one from the second array is copied first. The original order is thus broken. Re merged loops: with loops merged you need to evaluate a (totally redundant) condition on each iteration. – vnp Dec 29 '14 at 18:42

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.

• No arrays of runtime bound (aka variable-length arrays) up to and including C++14. – dyp Dec 29 '14 at 20:07
• @dyp: NO. Variable length arrays were not part of C++03. They were introduced into C99 but never taken on as part of C++. I know there was a lot of discussion of adding them to C++11 but I am not sure of the resolution and will need proof in the form of a standard quote (or a reliable blog post from somebody reliable Stroustrup/Alexandrescu/Sutter/Meyers). Now C++14 I could believe much more easily but would need a standard quote. Now a lot of compiler accepted them because (C and C++ compilers are closely intertwined) but only as a non standard extension. – Martin York Dec 30 '14 at 0:43
• OK. Variable length arrays were not in C++11 either. And they were remvoed from C++14 before release. But there is an alternative called std::dynarray which allocates locally and has a fixed size. stackoverflow.com/questions/17303902/… – Martin York Dec 30 '14 at 0:52
• I'm not sure how you interpreted my comment, what I wanted to say is "there are no arrays of runtime bound in C++, neither in C++98, nor C++03, nor C++11, nor C++14" – dyp Dec 30 '14 at 0:52
• @dyp: Yes I did interpret that incorrectly. Sorry. – Martin York Dec 30 '14 at 0:52