implementing merge sort c++

Hi I am trying to implement a merge sort on a vector which I pass into the function. Here is my code, it does not sort the list but I am not sure what is wrong. When I output the original vector and the sorted vector there are some differences between the two but it is still not sorted.

void BestFit::findBest(){
    vector<double> distances;
    vector<double> sorted;
    distances = getDistance(0);
    printDistance(distances);
    sorted = sortDistance(distances);
    printDistance(sorted);
}

vector<double> BestFit::sortDistance(vector<double> distances){
    int mid = distances.size()/2;
    vector<double> left;
    vector<double> right;

    if(distances.size() > 1){
        for(int i = 0; i < mid; i++){
            left.push_back(distances[i]);
        }

        for(int i = mid; i < distances.size(); i++){
            right.push_back(distances[i]);
        }
        return sortDistanceHelp(left, right);
    }else{
        return distances;
    }
}

vector<double> BestFit::sortDistanceHelp(vector<double> left, vector<double> right){
    vector<double> result;
    if(left.size() > 1){
        left = sortDistance(left);
    }else if(right.size() > 1){
        right = sortDistance(right);
    }

    int count = 0;
    int left_count = 0;
    int right_count = 0;
    while(count < (left.size() + right.size())){
        if(left_count < left.size() && right_count < right.size()){
            if(left[left_count] <= right[right_count]){
                result.push_back(left[left_count]);
                left_count++;
            }else{
                result.push_back(right[right_count]);
                right_count++;
            }
        }else if(left_count < left.size()){
            result.push_back(left[left_count]);
            left_count++;
        }else{
            result.push_back(right[right_count]);
            right_count++;
        }
        count++;
    }

    return result;
}

Here is the output of the unsorted and sorted distance vectors.

Unsorted:

Distance: 0.679371 Distance: 1.263918 Distance: 1.575268 Distance: 0.117904 Distance: 3.851347 Distance: 2.317885 Distance: 0.899686 Distance: 3.916363 Distance: 1.513004 Distance: 0.446430

Sorted:

Distance: 0.679371 Distance: 1.263918 Distance: 1.575268 Distance: 0.117904 Distance: 2.317885 Distance: 0.899686 Distance: 3.851347 Distance: 3.916363 Distance: 1.513004 Distance: 0.446430

Solution

I'm pretty sure this is the problem. In sortDistanceHelp():

if(left.size() > 1){
    left = sortDistance(left);
}else if(right.size() > 1){ //<<<===== ELSE SHOULD NOT BE HERE
    right = sortDistance(right);
}

It should read like this:

if(left.size() > 1)
    left = sortDistance(left);

if(right.size() > 1)
    right = sortDistance(right);

The rest of this is just a simple merge algorithm you can use for your own purposes that utilizes iterators. This is the simplest merge-algorithm I could muster. It relies on your data type to support operator <(), as well as operator =()

template<typename ForwardIterator, typename OutputIterator>
void mergelists
(
    ForwardIterator first1,     // starting iterator of first sequence
    ForwardIterator last1,      // ending iterator of first sequence
    ForwardIterator first2,     // starting iterator of second sequence
    ForwardIterator last2,      // ending iterator of second sequence
    OutputIterator out1)        // output iterator for results
{
    while (first1 != last1 && first2 != last2)
    {
        // note the opposing less-comparison. equtes to (i1 <= i2)
        while (first1 != last1 && !(*first2 < *first1))
            *out1++ = *first1++;

        if (first1 != last1)
        {
            while (first2 != last2 && *first2 < *first1)
                *out1++ = *first2++;
        }
    }

    // doesn't really matter which one finished first
    //  only one of these will put one or more final
    //  nodes into the sequence.
    while (first1 != last1)
        *out1++ = *first1++;
    while (first2 != last2)
        *out1++ = *first2++;
}

Coupled with a general mergesort algorithm taking a starting iterator and size, we have:

// general mergesort algorithm
template <typename Iterator>
void mergesort(Iterator first, size_t d)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;

    Iterator last = first + d;
    size_t n = d/2;
    if (n == 0)
        return;

    if (n > 1) // no single elements
        mergesort(first, n);
    if (d > 1) // no single elements
        mergesort(first+n, d-n);

    // merge back into local sequence
    std::vector<value_type> vals;
    vals.reserve(d);
    mergelists(first, first+n, first+n, last, back_inserter(vals));

    // and copy into where it all began
    std::copy(vals.begin(), vals.end(), first);
}

A sample usage of this with a random-filled vector is below:

int main()
{
    srand((unsigned)time(0));
    vector<int> data;

    // fill a vector with random junk.
    generate_n(back_inserter(data), 20, []() { return std::rand() % 99+1;});
    copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    mergesort(data.begin(), data.size());
    copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}

Sample Run I

54 75 14 59 69 18 65 40 52 77 65 43 87 80 99 44 81 40 70 37 
14 18 37 40 40 43 44 52 54 59 65 65 69 70 75 77 80 81 87 99

Sample Run II

53 91 27 29 47 31 20 90 12 18 16 75 61 94 60 55 66 44 35 26 
12 16 18 20 26 27 29 31 35 44 47 53 55 60 61 66 75 90 91 94