Your indexing leaves much to be desired. I will not be shy about telling you that, nor about saying simply that I would not do merge-sort this way. But it is what it is, so I'll cover it.
It is important to understand that sequence sorting using divide and conquer algorithms are all about passing some base reference within the sequence and some offsets from that reference. The algorithm should be independent of external variables (like array[]
and barray[]
) and take them as parameters instead. Further, remember you're programming in C++ (or C). Part of the beauty of both languages is their native pointer-arithmetic ability. It can be wonderfully used for algorithms like merge-sort. After I demonstrate how your merge and mergesort functions should work, I'll demonstrate what I'm talking about, then I'll proffer up the most-trivial merge sort you can do in C++ if you utilize the standard libraries functionality.
Your Code First
First a re-roll of your function using your parameters. I've taken the liberty of renaming the parameters to they're actually meaningful to the reviewer. The algorithm should be self-explanatory and I urge you to compare it side-by-side with what you were doing.
// low = starting index
// mid = middle index
// high = last index
void merge(int low, int mid, int high)
{
int i=low, j=mid, k=0;
while (i < mid && j <=high)
{
if (array[i] < array[j])
barray[k++] = array[i++];
else
barray[k++] = array[j++];
}
// finish whichever segment isn't done
while (i < mid)
barray[k++] = array[i++];
while (j <= high)
barray[k++] = array[j++];
// copy back
for (i=0;i<k;++i)
array[low+i] = barray[i];
}
void mergesort(int low, int high)
{
int len = high - low;
if (len < 2)
return;
int mid = low + len/2;
mergesort(low, mid);
mergesort(mid, high);
merge(low, mid, high);
}
Of note to this algorithm is the initial parameters passed must be valid indexes in the sequence. In other words, if you read an array of 8-elements, the valid indexes are 0..7
and therefore you would invoke it as mergesort(0,7)
.
A Different Approach
The traditional merge sort in C/C++ uses an array base-index and length as its only parameters. The midpoint is calculated by the sort-algorithm. Though it is not strictly needed for the merge algorithm, (it too can just use length/2), it makes for a more robust algorithm on the off-chance you ever need merging from a segment that is not split right now the middle.
Don't get hung up on the usage of std::vector, std::random_device, etc below. They're used in the main()
function solely to populate an array of random numbers that is then sorted, displayed both before and after the sort operation. What I want you to get out of this is the actual algorithm itself.
#include <iostream>
#include <vector>
#include <random>
void merge(int ar[], std::size_t mid, std::size_t len)
{
if (len < 2)
return;
// temporary storage. normally I use a RAII container
// such as std::vector<>, but I wanted to demonstrate
// the algorithm and indexing, not the memory management.
// none the less it is worth noting.
int *tmp = new int[len];
std::size_t i=0, j=mid, k=0;
while (i < mid && j < len)
{
if (ar[i] < ar[j])
tmp[k++] = ar[i++];
else
tmp[k++] = ar[j++];
}
// complete the unfinished segment
while (i < mid)
tmp[k++] = ar[i++];
while (j < len)
tmp[k++] = ar[j++];
// and move back to the original array
for (i=0; i<len; ++i)
ar[i] = tmp[i];
delete [] tmp;
}
void mergesort(int ar[], std::size_t len)
{
if (len < 2)
return;
// note pointer arithemtic in second call.
mergesort(ar, len/2);
mergesort(ar+len/2, len - len/2);
merge(ar, len/2, len);
}
int main()
{
std::vector<int> data;
data.reserve(20);
std::random_device rd;
std::default_random_engine rng(rd());
std::uniform_int_distribution<> dist(1,50);
// populate array
std::generate_n(std::back_inserter(data),
data.capacity(),
[&](){ return dist(rng);});
// show on-screen
for (auto n : data)
std::cout << n << ' ';
std::cout << '\n';
// mergesort
mergesort(data.data(), data.size());
// show on-screen
for (auto n : data)
std::cout << n << ' ';
std::cout << '\n';
return 0;
}
Output (varies)
15 10 8 38 20 21 9 43 8 22 19 45 12 16 17 36 2 32 6 37
2 6 8 8 9 10 12 15 16 17 19 20 21 22 32 36 37 38 43 45
The Part You'll Hate
After going through all this work you'll be not-so-happy to know that two algorithms that do segment merging for you are already present in the standard library, namely std::merge
and std::inplace_merge
. Using one of those makes implementing mergesort
trivial, as you'll see below:
#include <algorithm>
void mergesort(int ar[], std::size_t len)
{
if (len < 2)
return;
mergesort(ar, len/2);
mergesort(ar+len/2, len-len/2);
std::inplace_merge(ar, ar+len/2, ar+len);
}
Remember that if you ever need to use something besides std::sort
, which honestly puts all of this to a point of near-uselessness besides fulfilling academic purpose.