MergeSort Algorithm with Object Classes

Question 1

There are several faults in the code you post on codepad, I'll point out in the program comments. Since you didn't give us the definitions of Popular, Symphony and Opera, I'll have my own. For convenience, I put all the code in one file.

#pragma once
#include <string>
#include <iostream>

using namespace std;

class CD {
public:
    string publisher, title, location, year, empty;
public:
    CD()
    {
        publisher = "";
        title = "";
        location = "";
        year = "";
        empty = "";
    }

    void virtual input() = 0;

    void virtual output() = 0;
};


class Popular : public CD
{
public:
    Popular(const string& name)
    {
        title = name;
    }
    virtual void input()
    {
        return;
    }
    virtual void output()
    {
        return;
    }
};

void merge(CD *a[], int, int, int);

void merge_sort(CD *a[], int low, int high) {
    int mid;
    if (low < high) {
        mid = low + (high - low) / 2; //avoid overflow
        merge_sort(a, low, mid);
        merge_sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
}

void merge(CD *a[], int low, int mid, int high) {

    int p1 = low;
    int p2 = mid + 1;
    CD ** merged = (CD**)malloc(sizeof(CD*) * (high - low + 1)); // CD *b[high] isn't illegal c++ syntax, VLA is part of C99.
    int p = 0;
    while(p1 < mid + 1 && p2 < high + 1)
    {
        if(a[p1]->title > a[p2]->title)
        {
            merged[p] = a[p2];
            p2++;
        }
        else
        {
            merged[p] = a[p1];
            p1++;
        }
        p++;
    }

    while(p1 < mid + 1)
    {
        merged[p++] = a[p1++];
    }

    while(p2 < high + 1)
        merged[p++] = a[p2++];

    for(int i = 0;i < (high - low + 1); i++)
    {
        a[low + i] = merged[i];
    }

    free(merged);
}

int main() {
    CD *cdptr[100]; //pointer declaration for each of our class

    int n = 0, choose;

    // just to test the mergesort
    CD* c1 = new Popular("hello");
    CD* c2 = new Popular("world");
    CD* c3 = new Popular("coldplay");
    CD* c4 = new Popular("pink");

    cdptr[n++] = c1;
    cdptr[n++] = c2;
    cdptr[n++] = c3;
    cdptr[n++] = c4;

    char terminate = 'n'; // you should initialize this variable.

    do // do-while statement which allows the user to enter data and terminate the program when he wants
    {
        cout << "\n1.Classical";
        cout << "\n2.Popular";
        cout << "\n3.Sort";
        cout << "\n4.Display";
        cout << "\n5.Terminate program";
        cout << endl << endl;
        cout << "\nChoose category: ";
        cin >> choose;
        switch (choose)                            //switch for the user to choose the type of input
        {
            //skip the case 1, 2
            case 3:
                merge_sort(cdptr, 0, n - 1); //  element indices begin at 0.
                break;
            case 4:
                if (n == 0)
                    cout << "\nNo data entered!" << endl;
                for (int i = 0; i < n; i++) {
                    cdptr[i]->output();
                    cout << endl;
                }
                break;
            case 5:
                cout << "\nDo you want to terminate the program? (y/n)";
                cin >> terminate;
                break;
            default:
                cout << "\nNot recognized value!" << endl;
        }
    } while (terminate != 'y');

    for(int i = 0; i < 4; ++i)
        cout<<cdptr[i]->title<<endl;

    delete c1;
    delete c2;
    delete c3;
    delete c4;
    return 0;
}

Here's the output:

1.Classical  
2.Popular
3.Sort
4.Display
5.Terminate program


Choose category: 3

1.Classical
2.Popular
3.Sort
4.Display
5.Terminate program


Choose category: 5

Do you want to terminate the program? (y/n)y
coldplay
hello
pink
world

Question 2

Firstly, update your question to show your real code for merge, merge_sort and CD. I'll be referring to the actual code posted in the comments.

Your problem likely stems from you sorting the titles, as opposed to sorting based on the titles. Everywhere in your code where you are assigning the title of a CD to another, you are going wrong. You compare the titles, but you relocate and reorder the objects themselves (or in your case, the pointers to the objects themselves.)

Anyway, to fix this problem you just replace any code like this:

x->title = y->title;

with this:

x = y;

For example, instead of

b[i]->title = a[h]->title;

you should have written

b[i] = a[h];

By the way, memory allocation and deallocation is not something you do as an afterthought, to see whether it works or not! Even mediocre programmer treat memory with care; the good ones deal with memory with outright love and respect.