4
\$\begingroup\$

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;    
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Fixed indentation as it was imposable to read without it. \$\endgroup\$ May 3, 2014 at 0:11
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Jamal
    May 3, 2014 at 0:27
  • \$\begingroup\$ your code could be improved further but i think its an really good merge sorting c++ code \$\endgroup\$
    – user93792
    Jan 8, 2016 at 19:07

3 Answers 3

4
\$\begingroup\$

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
\$\endgroup\$
0
4
\$\begingroup\$
  • 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++.

\$\endgroup\$
0
3
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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