HiveBrain v1.2.0
Get Started
← Back to all entries
snippetcppMinor

Implementing the merge sort with only arrays, out of place

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thearraysmergewithplacesortimplementingonlyout

Problem

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 
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;    
}

Solution

-
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 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 values;

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


Pass it to a function with such parameters:

void merge_sort(std::vector 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++.

Code Snippets

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

values.push_back(2);
values.push_back(5);
// ...
void merge_sort(std::vector<int> values, int startIndex, int endIndex) {}

Context

StackExchange Code Review Q#48828, answer score: 4

Revisions (0)

No revisions yet.