I have studied the theory of the merge sort but don't have any idea of how to implement it in C++. My question is, merge sort creates arrays in recursion. But when implementing, how do we create arrays in runtime? or what is the general approach for this?
Thanks.
This is my version (simple and easy):
uses memory only twice the size of original array.
[ a is the left array ] [ b is the right array ] [ c used to merge a and b ] [ p is counter for c ]
void MergeSort(int list[], int size)
{
int blockSize = 1, p;
int *a, *b;
int *c = new int[size];
do
{
for (int k = 0; k < size; k += (blockSize * 2))
{
a = &list[k];
b = &list[k + blockSize];
p = 0;
for (int i = 0, j = 0; i < blockSize || j < blockSize;)
{
if ((j < blockSize) && ((k + j + blockSize) >= size))
{
++j;
}
else if ((i < blockSize) && ((k + i) >= size))
{
++i;
}
else if (i >= blockSize)
{
c[p++] = b[j++];
}
else if (j >= blockSize)
{
c[p++] = a[i++];
}
else if (a[i] >= b[j])
{
c[p++] = b[j++];
}
else if (a[i] < b[j])
{
c[p++] = a[i++];
}
}
for (int i = 0; i < p; i++)
{
a[i] = c[i];
}
}
blockSize *= 2;
} while (blockSize < size);
}