Merge sort

Typical example of a divide and conquer approach applied to the sorting problem. It's O(n lg n) time complexity makes it interesting for large enough data collections.

This algorithm's idea is that we could split recursively the problem until we have a tiny subproblem so simple that is trivial to solve it. Than we just have to merge the partial results to get the actual solution.

Here is the "divide" part, implemented in C++:

typedef std::vector<int> Data;

void mergeSort(Data& data, int left, int right) // 1
{
    if(left < right) // 2
    {
        int center = (left + right) / 2;
        mergeSort(data, left, center); // 3
        mergeSort(data, center + 1, right);
        merge(data, left, center, right); // 4
    }
}

1. The function expects in input the collection to sort and the first/last indexes to consider.
2. If there is just one element to sort, there is nothing to do.
3. Split the problem it two parts and recursively call the divide function on them.
4. Merge the partial solutions.

As one would expect, large part of the job is done by the merging function:

typedef std::queue<int> Queue;

void merge(Data& data, int left, int center, int right)
{
    Queue low; // 1
    Queue high;

    for(int i = left; i <= center; ++i) // 2
        low.push(data[i]);
    for(int i = center + 1; i <= right; ++i)
        high.push(data[i]);

    int i = left;
    while(!low.empty() && !high.empty()) // 3
    {
        if(low.front() <= high.front())
        {
            data[i++] = low.front();
            low.pop();
        }
        else
        {
            data[i++] = high.front();
            high.pop();
        }
    }

    while(!low.empty()) // 4
    {
        data[i++] = low.front();
        low.pop();
    }
    while(!high.empty())
    {
        data[i++] = high.front();
        high.pop();
    }
}

1. A couple of queues are used to temporary store the data while processing them.
2. Fill the queues with the data coming from the input collection.
3. Compare the data on the two queues, rearranging them in the original container.
4. Ensure all the possible elements left in the temporary queues are copied back to the input data.

Full code is on github. As bonus you will also find there a simple xUnit test for GoogleTest.