Merge Sort's running time in recursive version

Question

I learned that time function of merge sort is right below.

T(n) = 2T(n/2) + Θ(n) if n>1

I understand why T(n) = 2T(n/2)+ A

But why does A = Θ(n)?

I think A is maybe dividing time, but i don't understand why it is expressed as Θ(n)

Please help!

Answer 1

No, A is not the dividing step. A is the merging step which is linear.

void merge(int a[], int b[], int p, int q, int c[])
/* Function to merge the 2 arrays a[0..p} and b[0..q} into array c{0..p + q} */
{
    int i = 0, j = 0, k = 0;

    while (i < p && j < q) {
        if (a[i] <= b[j]) {
            c[k] = a[i];
            i++;
        }
        else {
            c[k] = b[j];
            j++;
        }
        k++;
    }
    while (i < p) {
        c[k] = a[i];
        i++;
        k++;
    }
    while (j < q) {
        c[k] = b[j];
        j++;
        k++;
    }
}

This merging step takes O(p + q) time when p and q are the subarray lengths and here p + q = n.