/*
 *  Also sorts
 */
void mergeSort(int * list, int low, int high)
{
    assert(low <= high);
    if (high - low == 1) return;

    int mid = (high - low) / 2, // Middle of the list.
        p = low,                // Point for the original list
        lp = 0,                 // Pointer for left list
        rp = 0,                 // Pointer for right list
        ln = mid - low,         // Length of left list
        rn = high - mid;        // Length of right list

    assert(mid - low + high - mid == high - low);

    int * left = new int[ln];
    int * right = new int[rn];

    // Populate left and right lists
    while (lp < ln)
        left[lp++] = list[p++];
    while (rp < rn)
        right[rp++] = list[p++];

    // Recursively call mergesort on left - right
    mergeSort(left, 0, mid);
    mergeSort(right, 0, high - mid);

    // reset pointers
    p = low;
    lp = 0;
    rp = 0;

    // Merge left and right
    while (lp < ln || rp < rn)
    {
        if (lp < ln && rp < rn)
        {
            if (left[lp] <= right[rp])
                list[p++] = left[lp++];
            else
                list[p++] = right[rp++];

        }
        else if (lp < ln)
            list[p++] = left[lp++];
        else
            list[p++] = right[rp++];
    }

    delete [] left;
    delete [] right;
}