Recurrent merge sort (without recursion)

Question

For educational purpose I implement recurrent merge sort without recursion. The algorithm idea seems absolutely clear but my implementation appears to be really slow:

• 5 seconds to sort 10,000 values;
• 6 minutes to sort 100,000 values;
• it was not able to finish 10,000,000 in several hours (while lib sort() function does it in aboit 6 seconds);

I guess, the problem is in my understanding of how C++ works. Maybe, I must not copy vectors to funtion and use pointers insted?

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>

void check_sort(std::vector<int> array); //test sorted arrays
void merge_sort(std::vector<int> array); //recurrent merge sort
std::vector<int> merge(std::vector<int> array, unsigned int b, unsigned int c, unsigned int e);

int main()
{
    unsigned int size;
    std::cout << "Please enter the size of your array:" << std::endl;
    std::cin >> size;

    std::vector<int> initial_array(size); //array of random elements

    //prefill arrays
    srand(time(0));
    for (unsigned int i; i < initial_array.size(); ++i) {
        initial_array[i] = rand();
    }

    merge_sort(initial_array);

 /* DEBUGGER
    std::cout << "initial array" << std::endl;
    for (unsigned int i = 0; i < initial_array.size(); ++i) {
        std::cout << initial_array[i] << " ";
    }
    std::cout << std::endl;
*/

    return 0;
}

void merge_sort(std::vector<int> array)
{
    std::cout << "merge sort" << std::endl;
    check_sort(array);
    /* DEBUGGER
    std::cout << "initial array" << std::endl;
    for (unsigned int i = 0; i < array.size(); ++i) {
        std::cout << array[i] << " ";
    } */

    float start_time =  clock();
    unsigned int n = array.size();
    for (unsigned int s = 1; s < n; s *= 2)
    {
        for (unsigned int b = 0; b < n; b += s*2)
        {
            unsigned int c = std::min(b + s - 1, n - 1);
            unsigned int e = std::min(c + s, n - 1);
            array = merge(array, b, c, e);
        }
    }
    float end_time = clock() - start_time;
    /* DEBUGGER
    for (unsigned int i = 0; i < array.size(); ++i) {
        std::cout << array[i] << " ";
    } */
    check_sort(array);
    std::cout << "time: " << end_time/1000 << std::endl;
}

std::vector<int> merge(std::vector<int> array, unsigned int b, unsigned int c, unsigned int e) {
    std::vector<int> C(array);
    unsigned int i1 = b; unsigned int i2 = c + 1; //start point in each piece
    unsigned int n1 = c; unsigned int n2 = e; //end point of each piece
    for (unsigned i = b; i <= e; ++i)
    {
        if (i1 > n1) //
        {
            C[i] = array[i2];
            ++i2;
        }
        else if (i2 > n2)
        {
            C[i] = array[i1];
            ++i1;
        }
        else if (array[i1] <= array[i2]) {
            C[i] = array[i1];
            ++i1;
        }
        else
        {
            C[i] = array[i2];
            ++i2;
        }
    }
    return C;
}


void check_sort(std::vector<int> array)
{
    for (unsigned int i = 0; i < (array.size() - 1); ++i)
    {
        if (array[i] > (array[i + 1]))
        {
            std::cout << "unsorted" << std::endl;
            return;
        }
    }
    std::cout << "sorted" << std::endl;
}

Answer 1

I see a number of things that may help you improve your code.

Rearrange the code to reduce the need for declarations

A function declaration is only needed by the compiler if it hasn't already encountered the function itself. With that said, if the functions in the file are in the order check_sort, merge, merge_sort and then main, no separate function declarations would be needed.

Separate I/O from logic

The check_sort routine is not bad as it is, but I'd advocate separating the I/O from the logic. That is, rename check_sort to is_sorted and have it return a bool value of true only if the vector is sorted. Leave the printing to the calling function instead.

Use const where practical

The check_sort function does not alter the passed vector, so that should be passed as const &:

void check_sort(const std::vector<int> &array)

Consider using references

While this code works, there is still some room for improvement. The easy thing to do to speed up the code is to simply use references like this:

std::vector<int> merge(std::vector<int> &array, unsigned int b, unsigned int c, unsigned int e) {

By having it &array instead of array you tell the compiler that it may use the passed object directly rather than making a copy. This single change makes the code run about twice as fast on my machine.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so it is not necessary to put return 0; explicitly at the end of main.

There's more, but that's all I have time for at the moment.

Answer 2

I followed the advice regarding references and the time really improved about twice but it still was too slow. Then I investigated every step of my algorithm to find out that copying a vector is really very heavy operation (~200 milliseconds to copy vector of 10,000,000 elements on my machine). That is, after using references I avoided first copy (when calling merge()) but there was still second one (when making temp copy for merging). So I tried to copy not entire vector but a part of it. Since there is a need to keep keys I used std::map. And the speed drastically increased. Numbers:

• 0.2 seconds to sort 10,000 values;
• 2.5 seconds to sort 100,000 values;
• 7.5 minutes to sort 10,000,000 (yes! it finally finished sorting!).

Here is the whole solution:

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <map>

void check_sort(const std::vector<int>& array); //test sorted arrays
void merge_sort(std::vector<int> array); //recurrent merge sort
void merge(std::vector<int>& array, unsigned int b, unsigned int c, unsigned int e);

int main()
{
    unsigned int size;
    std::cout << "Please enter the size of your array:" << std::endl;
    std::cin >> size;

    std::vector<int> initial_array(size); //array of random elements

    //prefill array
    srand(time(0));
    for (unsigned int i = 0; i < initial_array.size(); ++i) {
        initial_array[i] = rand();
    }

    merge_sort(initial_array);

    return 0;
}

void merge_sort(std::vector<int> array)
{
    std::cout << "merge sort" << std::endl;
    check_sort(array);

    float start_time =  clock();
    unsigned int n = array.size();
    for (unsigned int s = 1; s < n; s *= 2)
    {
        for (unsigned int b = 0; b < n; b += s*2)
        {
            unsigned int c = std::min(b + s - 1, n - 1);
            unsigned int e = std::min(c + s, n - 1);
            merge(array, b, c, e);
        }
    }
    float end_time = clock() - start_time;

    check_sort(array);
    std::cout << "merge sort time: " << end_time/1000 << std::endl;
}

void merge(std::vector<int>& array, unsigned int b, unsigned int c, unsigned int e) {
    std::map <unsigned int, int> C;
    for (unsigned int i = b; i <= e; ++i)
    {
        C.insert(std::pair<unsigned int, int> (i, array[i]));
    }
    unsigned int i1 = b; unsigned int i2 = c + 1; //start point in each piece
    unsigned int n1 = c; unsigned int n2 = e; //end point of each piece
    for (unsigned int i = b; i <= e; ++i)
    {
        if (i1 > n1) //
        {
            array[i] = C[i2];
            ++i2;
        }
        else if (i2 > n2)
        {
            array[i] = C[i1];
            ++i1;
        }
        else if (C[i1] <= C[i2]) {
            array[i] = C[i1];
            ++i1;
        }
        else
        {
            array[i] = C[i2];
            ++i2;
        }
    }
}


void check_sort(const std::vector<int>& array)
{
    for (unsigned int i = 0; i < (array.size() - 1); ++i)
    {
        if (array[i] > (array[i + 1]))
        {
            std::cout << "unsorted" << std::endl;
            return;
        }
    }
    std::cout << "sorted" << std::endl;
}