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;
}

• cHao: This would be a better question for SO, methinks...particularly if you consider the code slow enough to have failed. (For reference, though... yes, passing (and sometimes returning) vectors by value can cause problems. Pass by reference...and by const reference whenever you shouldn't need to modify the vector.)
• 200_success: I have rolled back Rev 3 → 1. Please see What to do when someone answers .

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.

• Nat: Is omitting 'return 0' really a good practice? I was taught to always return from my main() to support portability of my programs. And about declarations: I was also taught to first declare all my functions so I will never have problems rearranging them if my code grows and I reuse them. Is it really ok?
• Edward: Omitting return 0 has been supported by compilers for decades, so "portability" is not really a valid reason these days. As for declarations, after you get everything working and wish to, for example, move the code to separate interface (.h file) and implementation (.cpp file), then declarations are, of course needed. I prefer to debug everything first without them and then add them in when I separate the code into .h and .cpp files for reuse. Both are relatively minor points you're free to ignore if you prefer a different style.

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;
}