# mergesort wrong for large arrays – only some values are wrong why?

This is my mergesort algorithm:

``````#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#include <algorithm>
#include <iostream>

#include <cstdio>
#include <cstdlib>

#include <cmath>
#include <cstring>
#include <ctime>
#include <omp.h>
// Constants.h
#if !defined(MYLIB_CONSTANTS_H)
#define MYLIB_CONSTANTS_H 1

#endif

// Takes a sorted list of size n and a value, puts the value in one of n+1
// possible positions, if value is same to an element of the list take the
// position before the first occurence of the same element

binarysearchfindlowerrank(int *in, int n, int value, int projection) {

int *array = in + projection;

int L = 0;
int R = n;

while (R - L > 1) {

int middle = (R + L) / 2;

if (array[middle] == value) {
while (array[middle] == value && middle > 0) {

middle = middle - 1;
}

return middle + 1;
}
if (array[middle] < value) {
L = middle;
}
if (array[middle] > value) {
R = middle;
}
}

if (L == 0 && in[L] > value) {

return 0;
}
if (R == n && array[R - 1] < value) {

return n;
}
if (R == n && array[R - 1] >= value) {

return R - 1;
}
if (array[R] < value) {

return R + 1;
}
if (array[L] < value) {

return R;
}

return L;
}

// Takes a sorted list of size n and a value, puts the value in one of n+1
// possible positions, if value is same to an element of the list take the
// position after the last occurence of the same element

binarysearchfinduperrank(int *in, int n, int value, int projection) {

int *array = in + projection;
int L = 0;
int R = n;

while (R - L > 1) {

int middle = (R + L) / 2;

if (array[middle] == value) {
while (array[middle] == value && middle < n) {
middle = middle + 1;
}

return middle;
}
if (array[middle] < value) {
L = middle;
}
if (array[middle] > value) {
R = middle;
}
}

if (L == 0 && array[L] > value) {

return 0;
}
if (R == n && array[R - 1] <= value) {

return n;
}
if (R == n && array[R - 1] > value) {

return R - 1;
}
if (array[R] <= value) {

return R + 1;
}
if (array[L] <= value) {

return R;
}
}

/**
* helper routine: check if array is sorted correctly
*/
bool isSorted(int ref[], int data[], const size_t size) {
std::sort(ref, ref + size);
for (size_t idx = 0; idx < size; ++idx) {
}
for (size_t idx = 0; idx < size; ++idx) {
if (ref[idx] != data[idx]) {
printf("\nFalscher Index:%d\n", idx);
printf("\n[");
for (size_t idx = 0; idx < size; ++idx) {
printf("%d,", ref[idx]);
}
printf("]\n");

printf("\n[");
for (size_t idx = 0; idx < size; ++idx) {
printf("%d,", data[idx]);
}
printf("]\n");
return false;
}
}
return true;
}

/**
* sequential merge step (straight-forward implementation)
*/
void MsMergeSequential(int *out, int *in, long begin1, long end1, long begin2,
long end2, long outBegin, int *data, int *tmp) {

if (begin1 == end2) {
out[begin1] = in[begin1];
}
if (begin1 == begin2 || begin2 == end2) {

out[begin1 + binarysearchfinduperrank(in, 1, in[end2], begin1)] = in[end2];
out[begin1 + binarysearchfindlowerrank(in, 1, in[begin1], end2)] =
in[begin1];

}

else {

for (int i = 0; i < (end2 - begin2); i++) {

out[begin1 + i +
binarysearchfinduperrank(in, (end1 - begin1), in[begin2 + i],
begin1)] = in[begin2 + i];
}
for (int i = 0; i < (end1 - begin1); i++) {
out[begin1 + i +
binarysearchfindlowerrank(in, (end2 - begin2), in[begin1 + i],
begin2)] = in[begin1 + i];
}
}
}
bool myfunc(long i, long j) { return (i < j); }
/**
* sequential MergeSort
*/
void MsSequential(int *array, int *tmp, bool inplace, long begin, long end) {
if (begin < (end - 1)) {
long half = (begin + end) / 2;

{

MsSequential(array, tmp, !inplace, begin, half);

MsSequential(array, tmp, !inplace, half, end);
}
if (inplace) {
MsMergeSequential(array, tmp, begin, half, half, end, begin, array, tmp);

} else {
MsMergeSequential(tmp, array, begin, half, half, end, begin, array, tmp);
}

} else if (!inplace) {

tmp[begin] = array[begin];
}
}

/**
* Serial MergeSort
*/
void MsSerial(int *array, int *tmp, const size_t size) {

MsSequential(array, tmp, true, 0, size);
}

/**

/**
* @brief program entry point
*/
int main(int argc, char *argv[]) {
// variables to measure the elapsed time
struct timeval t1, t2;
double etime;

// expect one command line arguments: array size
if (argc != 2) {
printf("Usage: MergeSort.exe <array size> \n");
printf("\n");
return EXIT_FAILURE;
} else {
const size_t stSize = strtol(argv[1], NULL, 10);
int *data = (int *)malloc(stSize * sizeof(int));
int *tmp = (int *)malloc(stSize * sizeof(int));
int *ref = (int *)malloc(stSize * sizeof(int));
printf("Initialization...\n");

srand(95);

for (size_t idx = 0; idx < stSize; ++idx) {
data[idx] = (int)(stSize * (double(rand()) / RAND_MAX));
}

std::copy(data, data + stSize, ref);

double dSize = (stSize * sizeof(int)) / 1024 / 1024;
printf("Sorting %zu elements of type int (%f MiB)...\n", stSize, dSize);

gettimeofday(&t1, NULL);

{

{ MsSerial(data, tmp, stSize); }
}
gettimeofday(&t2, NULL);
etime = (t2.tv_sec - t1.tv_sec) * 1000 + (t2.tv_usec - t1.tv_usec) / 1000;
etime = etime / 1000;

printf("done, took %f sec. Verification...", etime);
if (isSorted(ref, data, stSize)) {
printf(" successful.\n");
} else {
printf(" FAILED.\n");
}

free(data);
// delete[] data;
free(tmp);
// delete[] tmp;
free(ref);
// delete[] ref;
}

return EXIT_SUCCESS;
}
``````

The output is almost correct only some values are wrong,the farther one goes the more failurs occur and for small arrays the algorithm is correct, can anyone explain why?

Output for 800, the first array is the correct reference array and the second array is the array with my mergesort algorithm:

``````first wrong index:0

[0,2,3,5,6,8,8,9,10,10,10,11,11,12,12,12,14,15,15,15,16,17,18,19,19,20,20,21,21,21,23,25,25,26,26,27,29,35,35,35,36,38,39,40,40,42,42,46,46,49,50,51,52,53,54,55,55,58,58,61,61,62,63,65,66,67,67,68,70,71,72,72,74,75,76,78,78,79,81,81,82,84,85,85,85,86,86,87,87,88,88,88,89,91,95,95,97,99,99,100,100,101,101,103,104,104,104,104,105,105,105,106,107,107,108,108,108,110,111,111,115,115,117,117,118,119,119,119,120,123,123,123,124,124,124,125,126,126,128,129,131,131,131,132,132,133,134,135,136,139,139,141,141,142,142,143,144,144,144,144,148,148,149,151,151,152,152,153,153,155,157,157,157,159,160,163,164,164,165,165,166,167,168,169,171,172,172,175,176,176,176,178,178,179,180,180,180,181,182,182,183,185,186,187,188,189,194,196,197,197,199,200,201,204,205,206,206,211,212,213,213,213,214,214,214,215,215,216,217,218,218,219,219,220,221,222,223,225,226,227,227,228,228,228,229,230,233,233,237,238,238,240,240,241,243,243,243,243,244,245,246,248,249,249,250,251,251,253,255,255,257,257,259,259,260,263,266,267,268,268,268,270,271,271,271,272,273,274,276,276,276,276,279,280,280,280,281,281,281,281,282,282,283,283,284,285,288,289,290,293,295,297,299,299,300,300,301,302,304,304,305,306,307,307,307,308,308,308,308,309,309,310,310,311,311,312,312,313,314,314,314,315,316,316,317,317,319,319,319,320,321,321,322,323,324,324,327,327,328,329,329,329,329,330,331,331,332,332,334,336,337,338,338,339,339,339,342,347,347,349,351,352,352,352,352,353,353,353,354,355,357,360,361,363,363,364,364,365,365,366,366,369,372,375,375,377,378,379,381,381,384,388,392,393,394,395,395,397,397,398,398,398,399,400,401,403,403,405,405,405,405,406,406,409,409,410,411,411,412,412,412,413,415,415,416,420,420,420,420,421,422,422,422,422,423,423,424,426,433,434,434,435,435,435,436,438,438,443,449,450,450,454,455,457,458,459,460,460,460,462,462,466,468,468,470,470,472,473,474,475,477,478,478,481,484,486,487,487,490,491,492,492,492,493,494,495,495,498,498,499,499,500,502,505,505,506,506,506,507,509,509,509,509,510,511,511,512,513,514,517,517,518,520,520,521,522,522,522,523,523,524,525,525,526,526,526,528,528,530,530,531,531,532,532,534,535,536,537,537,538,541,541,541,544,544,547,547,551,552,553,555,557,558,561,562,564,565,566,566,568,569,570,571,571,572,573,573,575,575,578,579,586,586,586,587,587,587,587,587,588,588,589,591,591,591,592,594,594,594,595,596,597,597,598,598,599,599,599,601,601,601,602,602,603,608,608,609,611,612,612,613,614,615,616,619,619,619,621,621,621,623,624,625,626,626,626,627,629,629,630,630,631,632,632,633,633,633,634,636,636,639,641,645,646,647,647,648,651,652,652,653,654,655,655,658,659,659,660,662,662,663,664,665,667,667,667,668,668,669,669,669,670,670,673,673,678,678,682,682,683,683,684,684,685,686,687,688,689,690,691,692,693,694,694,695,695,695,696,697,697,698,699,700,703,706,708,709,710,711,711,717,718,719,719,721,724,726,728,729,730,730,732,734,735,735,736,739,739,740,741,745,747,748,750,750,751,752,755,756,756,760,761,762,764,766,767,768,769,769,770,770,771,772,772,777,777,777,780,781,781,783,783,786,786,786,787,787,788,789,789,789,790,790,790,791,791,793,793,794,794,]

[2,3,5,6,8,8,9,15,10,10,10,11,11,12,12,12,14,15,15,15,16,17,18,19,19,20,20,21,21,21,23,25,25,26,26,27,29,35,35,35,36,38,39,40,40,42,42,46,46,49,50,51,52,53,54,55,55,58,58,61,61,62,63,65,66,67,67,68,70,71,72,72,74,75,76,78,78,79,81,81,82,84,85,85,85,86,86,87,87,88,88,88,89,91,95,95,97,99,99,100,100,101,101,103,104,104,104,104,105,105,105,106,107,107,108,108,108,110,111,111,115,115,117,117,118,119,119,119,120,123,123,123,124,124,124,125,126,126,128,129,131,131,131,132,132,133,134,135,136,139,139,141,141,142,142,143,144,144,144,144,148,148,149,151,151,152,152,153,153,155,157,157,157,159,160,163,164,164,165,165,166,167,168,169,171,172,172,175,176,176,176,178,178,179,180,180,180,181,182,182,183,185,186,187,188,189,194,196,197,197,199,200,201,204,205,206,206,211,212,213,213,213,214,214,214,215,215,216,217,218,218,219,219,220,221,222,223,225,226,227,227,228,228,228,229,230,233,233,237,238,238,240,240,241,243,243,243,243,244,245,246,248,249,249,250,251,251,253,255,255,257,257,259,259,260,263,266,267,268,268,268,270,271,271,271,272,273,274,276,276,276,276,279,280,280,280,281,281,281,281,282,282,283,283,284,285,288,289,290,293,295,297,299,299,300,300,301,302,304,304,305,306,307,307,307,308,308,308,308,309,309,310,310,311,311,312,312,313,314,314,314,315,316,316,317,317,319,319,319,320,321,321,322,323,324,324,327,327,328,329,329,329,329,330,331,331,332,332,334,336,337,338,338,339,339,339,342,347,347,349,351,352,352,352,352,353,353,353,354,355,357,360,361,363,363,364,364,365,365,366,366,369,372,375,375,377,378,379,381,381,384,388,392,393,394,395,395,397,397,398,398,398,399,400,401,403,403,405,405,405,405,406,406,409,409,410,411,411,412,412,412,413,415,415,416,420,420,420,420,421,422,422,422,422,423,423,424,426,433,434,434,435,435,435,436,438,438,443,449,450,450,454,455,457,458,459,460,460,460,462,462,466,468,468,470,470,472,473,474,475,477,478,478,481,484,486,487,487,490,491,492,492,492,493,494,495,495,498,498,499,499,500,502,505,505,506,506,506,507,509,509,509,509,510,511,511,512,513,514,517,517,518,520,520,521,522,522,522,523,523,524,525,525,526,526,526,528,528,530,530,531,531,532,532,534,535,536,537,537,538,541,541,541,544,544,547,547,551,552,553,555,557,558,561,562,564,565,566,566,568,569,570,571,571,572,573,573,575,575,578,579,586,586,586,587,587,587,587,587,588,588,589,591,591,591,592,594,594,594,595,596,597,597,598,598,599,599,599,601,601,601,602,602,603,608,608,609,611,612,612,613,614,615,616,619,619,619,621,621,621,623,624,625,626,626,626,627,629,629,630,630,631,632,632,633,633,633,634,636,636,639,641,645,646,647,647,648,651,652,652,653,654,655,655,658,659,659,660,662,662,663,664,665,667,667,667,668,668,669,669,669,670,670,673,673,678,678,682,682,683,683,684,684,685,686,687,688,689,690,691,692,693,694,694,695,695,695,696,697,697,698,699,700,703,706,708,709,710,711,711,717,718,719,719,721,724,726,728,729,730,730,732,734,735,735,736,739,739,740,741,745,747,748,750,750,751,752,755,756,756,760,761,762,764,766,767,768,769,769,770,770,771,772,772,777,777,777,780,781,781,783,783,786,786,786,787,787,788,789,789,789,790,790,790,791,791,793,793,794,794,]
``````