Merge Sort doesn't work properly
Mar 17, 2013 at 11:43am UTC
I've tried to grasp the concept of merge sort, so decided to write an algorithm for it however in most cases, instead of returning sorted sequence of numbers, it returns zeros between numbers. I think, that problem may be in loop, that merges two sequences, however, I can't really find where exactly. Maybe fresh eyes can spot something. Here is the code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
int * MergeSort (int inSequenceSize, int * inSequence)
{
// split
int Size1 = inSequenceSize / 2;
int Size2 = inSequenceSize - Size1;
if (Size1 == 0)
return inSequence;
int * Sequence1 = new int [Size1];
int * Sequence2 = new int [Size2];
for (int i = 0; i < Size1; i++)
Sequence1[i] = inSequence[i];
for (int i = 0; i < Size2; i++)
Sequence2[i] = inSequence[i + Size1];
// recurrent call:
Sequence1 = MergeSort(Size1, Sequence1);
Sequence2 = MergeSort(Size2, Sequence2);
// merge
int * reSequence = new int [inSequenceSize];
int id1 = 0;
int id2 = 0;
for (int i = 0; i < inSequenceSize; i++) // <-- merge loop
{
if (id1 > Size1)
{
reSequence[i] = Sequence2[id2];
id2++;
continue ;
}
if (id2 > Size2)
{
reSequence[i] = Sequence1[id1];
id1++;
continue ;
}
if (Sequence1[id1] > Sequence2[id2])
{
reSequence[i] = Sequence2[id2];
id2++;
}
else
{
reSequence[i] = Sequence1[id1];
id1++;
}
}
return reSequence;
}
Topic archived. No new replies allowed.