MergeSort - std :: bad_alloc lanzado al intentar asignar vector

Question

Buenas tardes señoras y caballeros. Entonces, no es mi día de errores. Implementación de Mergesort (no en el lugar) en C ++, y tengo problemas reales con el código, sin ni idea de por qué. La segunda línea de la mergeSort() la función asigna el resultado del merge() a un vector de ints, result. Esta línea (la asignación real, no la función) arroja un bad_alloc Error, y no tengo idea de por qué.

Internet sugiere que bad_alloc se arroja principalmente debido a errores fuera de memoria, pero este no puede ser el caso, ya que la primera vez que se llama está en un vector de 500 ints, que no debería estar casi demasiado memoria (¿qué es eso, como 2 kb en un 32 bit int?). Supongo que estoy haciendo algo tonto e incorrecto para C ++, pero no sé qué. Intenté llamar what() En la excepción, pero eso solo devuelve su nombre. El código:

vector<int> Sorting::mergeSort(vector<int> A) {

    // If the length of A is 0 or 1, it is sorted.
    if(A.size() < 2) return A;

    // Find the mid-point of the list.
    int midpoint = A.size() / 2;

    // Declare the left/right vectors.
    vector<int> left, right;

    // Declare the return vector.
    vector<int> result (A.size());

    for(int i = 0; i < midpoint; ++i) {
        left.push_back(A.at(i));
    }

    for(int i = midpoint; i < A.size(); ++i) {
        right.push_back(A.at(i));
    }

    left = mergeSort(left);
    right = mergeSort(right);
    result = merge(left, right);

    return result;

}


vector<int> merge(vector<int> left, vector<int> right) {

    vector<int> result;

    while(left.size() > 0 && right.size() > 0) {

        if(left.front() <= right.front()) {
            result.push_back(left.front());
            left.erase(left.begin());
        } else {
            result.push_back(right.front());
            right.erase(right.begin());
        }
    }

    if(left.size() > 0) {
        for(int i = 0; i < left.size(); ++i) {
            result.push_back(left.at(i));
        }
    } else {
        for(int i = 0; i < right.size(); ++i) {
            result.push_back(right.at(i));
        }
    }

}

Si reescribo el merge función para tomar una referencia a result Y editarlo durante la función, funciona bien, pero quería mantener el código lo más cerca posible para el código de psedo 'estándar' dado para la fusión.

Agradezco cualquier ayuda, gracias.

Answer 1

En el Merge función, vector<int> result no está siendo devuelto.