# Implementing the merge sort with only arrays, out of place

This has been asked a few times here, but I was wondering what I could do to improve the efficiency and readability of my code. My programming skill has gotten rusty, so I would like to elicit all constructive criticism that can make me write code better.

init:

#include <iostream>
using namespace std;


merge()

//The merge function
void merge(int a[], int startIndex, int endIndex)
{

int size = (endIndex - startIndex) + 1;
int *b = new int [size]();

int i = startIndex;
int mid = (startIndex + endIndex)/2;
int k = 0;
int j = mid + 1;

while (k < size)
{
if((i<=mid) && (a[i] < a[j]))
{
b[k++] = a[i++];
}
else
{
b[k++] = a[j++];
}

}

for(k=0; k < size; k++)
{
a[startIndex+k] = b[k];
}

delete []b;

}


merge_sort()

//The recursive merge sort function
void merge_sort(int iArray[], int startIndex, int endIndex)
{
int midIndex;

//Check for base case
if (startIndex >= endIndex)
{
return;
}

//First, divide in half
midIndex = (startIndex + endIndex)/2;

//First recursive call
merge_sort(iArray, startIndex, midIndex);

//Second recursive call
merge_sort(iArray, midIndex+1, endIndex);

//The merge function
merge(iArray, startIndex, endIndex);

}


main()

//The main function
int main(int argc, char *argv[])
{
int iArray = {2,5,6,4,7,2,8,3,9,10};

merge_sort(iArray, 0, 9);

//Print the sorted array
for(int i=0; i < 10; i++)
{
cout << iArray[i] << endl;
}

return 0;
}

• Fixed indentation as it was imposable to read without it. May 3, 2014 at 0:11
• @LokiAstari: As much as I dislike the indentation issue as well, it is not from tabs and I have already reviewed it. You may keep a better version for yourself if you're going to review it. May 3, 2014 at 0:27
• your code could be improved further but i think its an really good merge sorting c++ code
– user93792
Jan 8, 2016 at 19:07

Everything Jamal said (so I will not repeat)

Plus:

The normal idium in C++ for passing ranges is [beg, end).
For those not mathematically inclined end is specified one past the end.

If you follow the C++ convention you make it easier for other C++ devs to keep track without having to think to hard about what you are up to. Personally I think it also makes writting merge sort easier.

 merge_sort(iArray, 0, 10);


Then in merge()

 midIndex = (startIndex + endIndex)/2;     // The start of the second half
// Is one past the end of the first half.
merge_sort(iArray, startIndex, midIndex);
merge_sort(iArray, midIndex,   endIndex);


Slight optimization here:

//Check for base case
if (startIndex >= endIndex)
{
return;
}


You can return if the size is 1. A vector of 1 is already sorted. Since end is one past the end the size is end-start.

if ((endIndex - startIndex) <= 1)
{
return;
}


Don't do manually memory management in your code.

int *b = new int [size](); // Also initialization costs.
// So why do that if you don't need to!

// PS in C++ (unlike C)
// It is more common to put '*' by the type.
// That's becuase the type is pointer to int


Better alternative:

std::vector<int> b(size);  // Memory management handled for you.
// Its exception safe (so you will never leak).


A conditional in the middle of a loop is expensive.

while (k < size)
{
if((i<=mid) && (a[i] < a[j]))
{...} else {...}
}


Once one side is used up break out of the loop and just copy the other one.

while (i <= mid && j <= endIndex)
{    b[k++] = (a[i] < a[j]) ? a[i++] : a[j++];
}
// Note: Only one of these two loop will execute.
while(i <= mid)
{    b[k++] = a[i++];
}
while(j <= endIndex)
{    b[k++] = a[j++];
}


Rather than calculating the mid point both in merge() and in merge_sort, it may be worth just passing the value as a parameter.

Learn to do the inplace merge so you don't have to copy the values back after the merge.

 midIndex = (startIndex + endIndex)/2;
merge_sort(iArray, startIndex, midIndex);
merge_sort(iArray, midIndex,   endIndex);
merge(iArray, startIndex, midIndex, endIndex);
//                        ^^^^^^^^   pass midIndex so you don't need to re-calc

• Code within a function should be indented as well. You already do this with other code blocks, and the same applies to functions.

• Just avoid Hungarian notation:

int iArray;


We already know it's an int array.

• Prefer not to pass C arrays to functions in C++. This causes them to decay to a pointer; it does not actually pass the array itself.

Instead, pass in a storage container, such as an std::vector. Storage containers will not decay to a pointer, and they're more idiomatic C++.

If you have C++11, initialize the vector using list initialization:

std::vector<int> values { 2, 5, 6, 4, 7, 2, 8, 3, 9, 10 };


If you don't have C++11, declare it and call push_back() for each value:

std::vector<int> values;

values.push_back(2);
values.push_back(5);
// ...


Pass it to a function with such parameters:

void merge_sort(std::vector<int> values, int startIndex, int endIndex) {}


As its implementation is that of an array, you can still access its elements with []. You can also use its iterators (more preferred).

Storage containers do the memory allocation for you, so you will not need new/delete. It's best to do as little manual memory allocation as possible in C++.

Most of the interesting points has been covered already. The missing one:

merge is an important algorithm of its own. As implemented, it imposes very harsh and non-obvious preconditions. Relax them:

void merge(int b[], int a0[], int size0, int a1[], int size1);


and let the caller decide how to allocate/delete/reuse the b array. Notice that in the context of mergesort the caller is you, so the caller of mergesort wouldn't see the difference.

PS: a no raw loops rule is also perfectly applicable. A loop:

for(k=0; k < size; k++)
{
a[startIndex+k] = b[k];
}


in fact implements an important algorithm known as copy(int * a, int * b, int size), and is better be factored out as such.

• Thank you! I wasn't aware of this. Read about the no raw loops rule just now, and it makes sense.
– KKP
May 4, 2014 at 4:11