Implementing the merge sort with only arrays, out of place

Question

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[10] = {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;    
}

Answer 1

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).
                           // Overhead is insignificant.

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

Answer 2

• Try not to use using namespace std.

• 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++.

Answer 3

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.