Bdtjtk

Here is the code. I simply did a merge sorting using a Divide and Conquer algorithm but it doesn't work and i haven't found why. I'm passing an unordered vector, 0 and vector.size() to the mergeSort function.

#include <iostream>

#include <vector>

#include <algorithm>



template<typename T>

void directInsertion(std::vector<T>& vec, int start, int end);



template<typename T>

void merge (std::vector<T>& vec, int left, int middle, int right);



template<typename T>

void mergeSort(std::vector<T>& vec, int left, int right);



template<typename T>

void directInsertion(std::vector<T>& vec, int start, int end)

{

    T value = T();

    int i;

    int j;



    for(i = start + 1; i < end; ++i)

    {

        value = vec[i];

        for(j = i - 1; j >= 0 && !(vec[j] < value); --j)

            vec[j + 1] = vec[j];

        vec[j + 1] = value;

    }

}



template<typename T>

void mergeSort(std::vector<T>& vec, int left, int right)

{

    int length = right - left;



    if(length <= 3)

        directInsertion(vec, left, right);

    else

    {

        int middle = left + (length >> 1);

        mergeSort(vec, left, middle);

        mergeSort(vec, middle, right);

        merge(vec, left, middle, right);

    }

}



template<typename T>

void merge (std::vector<T>& vec, int left, int middle, int right)

{

    int length = right - left;

    int p = left;

    int q = middle + 1;



    std::vector<T> tmp;



    for(size_t l = 0; l < length; ++l) {

        if (p <= middle && (q >= right || vec.at(p) <= vec.at(q)))

            tmp.push_back(vec.at(p++));

        else

            tmp.push_back(vec.at(q++));

    }

    for(size_t l = 0; l < length; ++l)

        vec.at(left + l) = tmp.at(l);

}



void printMessage(bool passed, const char* message)

{

    if(passed)

        std::cout << message << "............... PASS" << std::endl;

    else

        std::cout << message << "............... FAIL" << std::endl;

}



void printVector(std::vector<int>& v)

{

    std::cout << "[";

    for(auto i: v)

        std::cout << " " << i << " ,";

    std::cout << "]";

}



int main()

{

    std::vector<int> v = {1, 2, 3, 4};

    std::vector<int> orderedVector = v;

    std::vector<int> aux;



    bool passed = true;



    do {

        aux = v;

        mergeSort(aux, 0, aux.size());

        if(aux != orderedVector)

        {

            printVector(aux);

            std::cout << " != ";

            printVector(orderedVector);

            std::cout << std::endl;

            passed = false;

        }

    } while(std::next_permutation(v.begin(), v.end()) && passed);



    printMessage(passed, "MERGE SORT");

}

There may be other problems, but this line needs to be fixed:

        mergeSort(vec, middle + 1, right);

changed to

        mergeSort(vec, middle, right);

I would also suggest using the names begin and end instead of left and right, to be consistent with the naming convention used for vector iterators, and because the "right" iterator or index points to the "end" of a vector or array, 1 past the last element of the array.