Merge part of mergesort

May 31, 2021 at 5:19pm
Hello guys. I have the following code for mergesort:

1
2
3
4
5
6
7
8
9
void merge(T a[], int l, int m, int r)
{ int i, j;
static T aux[maxN];
for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
for (int k = l; k <= r; k++)
if (aux[j] < aux[i])
a[k] = aux[j--]; else a[k] = aux[i++];
}


I would like to ask you the following. Is it possible for the part

static T aux[maxN]

to be functional? I mean my code does not compile because the compiler says that the array must have an defined size (reasonable). However, my textbook considers aux[maxN] in the merge code. Pleae note that aux[maxN] is the auxiliary array into which the inital array is copied.
Last edited on May 31, 2021 at 5:21pm
May 31, 2021 at 5:53pm
Just make sure that maxN is defined const.
May 31, 2021 at 5:56pm
Thanks lastchance. Do you mean something like this?

static const T aux[maxN];
May 31, 2021 at 6:01pm
No, I mean that maxN is defined const, not aux.
const int maxN=100; //or whatever.

If you don't want to do that then you would have to use dynamic arrays or std:: vector
Last edited on May 31, 2021 at 6:03pm
May 31, 2021 at 8:20pm
You're right lastchance. My mistake. Thank you again for your help!
Jun 1, 2021 at 5:52pm
It's best to allocate the extra space dynamically (perhaps as a vector) in the mergesort function and pass it to merge. That way you can set it's size appropriately and only need to allocate/deallocate once.

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(T a[], int l, int m, int r, T b[]);

void mergesort(T a[], int start, int end) {
    T *b = new T[size];
    if (...) {
        // should switch to insertion sort for a small number of elements
        int mid = start + (end - start) / 2; 
        mergesort(a, start, mid);
        mergesort(a, mid + 1, end);
        merge(a, start, mid, end, b);
    }
    delete[] b;
}

Topic archived. No new replies allowed.