How can I make this c++ program faster?

Question

I am trying to sort strings using merge sort and standard string comparison. The problem is, this program is very slow as is. I am exceeding runtime expectations when I am attempting to check my solution. Is there a way I can use some other data structure to do the same thing but be accessed faster? Here is the code. Thank you for your help.

Edit: I understand that using sort() rather than my own merge sort algorithm will be faster, but my requirement states to use merge sort. The problem is exceeding runtime requirements on SPOJ.

#include <iostream>
using namespace std;

void MergeSortA(int low , int high);
void MergeA(int low ,int mid ,int high);

string stringData[50000];
int main()
{
    int testCases;
    int linesInTestCase;

    scanf("%d", &testCases);
    while(testCases--)
    {
        scanf("%d", &linesInTestCase);
        for(int i = 0; i < linesInTestCase; ++i)
            cin >> stringData[i];

        // Sort the data
        MergeSortA(0, linesInTestCase - 1);

        // Print array of strings one by one
        for(int i = 0; i < linesInTestCase; ++i) {
            cout << stringData[i] << endl;
        }
    }
    return 0;
}

void MergeSortA(int low , int high)
{
    int mid = 0;
    if(low < high)
    {
        mid = ((low+high)/2);
        MergeSortA(low , mid);
        MergeSortA(mid+1,high);
        MergeA(low,mid,high);
    }
}
void MergeA(int low ,int mid , int high)
{
    int i = low, j = mid+1 , k = low;
    string Temp[50000];

    while(i <= mid && j <= high) {
        if( stringData[i] < stringData[j] ) {
            Temp[k].assign(stringData[i]);
            i++;
        }
        else {
            Temp[k].assign(stringData[j]);
            j++;
        }
        k++;
    }

    if(i > mid ) {
        for(int h = j ;h <= high ; h++ ) {
            Temp[k].assign(stringData[h]);
            k++;
        }
    }
    else
        for(int h = i; h<= mid ; h++ ) {
            Temp[k].assign(stringData[h]);
            k++;
        }

    // Copy from low to high
    for(int l = low; l <= high ; l++) {
        stringData[l].assign(Temp[l]);
    }
}

Answer 1

As you stated that this is SPOJ problem, I will try not alter your structure of your program, However, there is real bottleneck here:

void MergeA(int low ,int mid , int high)
{
    int i = low, j = mid+1 , k = low;
    string Temp[50000]; //<--- Allocation happens every time this function is called

Wnenever MergeA is called, 50000 strings are constructed & destructed every time, encumbering the algorithm. Just add static there:

void MergeA(int low ,int mid , int high)
{
    int i = low, j = mid+1 , k = low;
    static string Temp[50000]; //Now it is constructed & destructed only once in the program