implementing merge sort in C

0 votes
I've studied the theory of the merge sort, but I'm not sure how to implement it in C++. My question is if merge sort generates arrays recursively. But how can we construct arrays in runtime while implementing? Alternatively, what is the usual approach to this?
Jun 9 in C++ by Nicholas
• 2,460 points
19 views

1 answer to this question.

0 votes

To respond to the question: 

std::vectorT> is used to create dynamically sized arrays at runtime. 

Ideally, you'd use one of these to get feedback. 

If not, they are simple to convert. 

For instance, you might make two arrays like this:

template <typename T>
void merge_sort(std::vector<T>& array) {
    if (1 < array.size()) {
        std::vector<T> array1(array.begin(), array.begin() + array.size() / 2);
        merge_sort(array1);
        std::vector<T> array2(array.begin() + array.size() / 2, array.end());
        merge_sort(array2);
        merge(array, array1, array2);
    }
}

However, allocating dynamic arrays is relatively slow and generally should be avoided when possible. For merge sort you can just sort subsequences of the original array and in-place merge them. It seems, std::inplace_merge() asks for bidirectional iterators.

answered Jun 10 by Damon
• 3,580 points

Related Questions In C++

0 votes
1 answer

What data structure is inside std::map in C++?

An associative container is std::map. The standard's ...READ MORE

answered May 31 in C++ by Damon
• 3,580 points
19 views
0 votes
1 answer

Easiest way to convert int to string in C++

C++ adds std::stoi (and variants for each numeric type) and std::to string, which are the C equivalents of atoi and itoa but expressed in terms of std::string #include <string> std::string s = std::to_string(42); Is therefore ...READ MORE

answered Jun 1 in C++ by Damon
• 3,580 points
25 views
0 votes
1 answer

Using getline() in C++

If you use getline() after cin >> anything, you must first flush the newline character from the buffer.  You can achieve this by using the cin.ignore() It would be something like this: string messageVar; cout ...READ MORE

answered Jun 1 in C++ by Damon
• 3,580 points
16 views
0 votes
0 answers

How to traverse stack in C++?

Is traversing std::stack possible in C++? It is not possible to traverse using the following method.  Because there is no member end in std::stack. std::stack<int> foo; // .. for (__typeof(foo.begin()) it = foo.begin(); ...READ MORE

Jun 1 in C++ by Nicholas
• 2,460 points
25 views
+15 votes
2 answers

Git management technique when there are multiple customers and need multiple customization?

Consider this - In 'extended' Git-Flow, (Git-Multi-Flow, ...READ MORE

answered Mar 27, 2018 in DevOps & Agile by DragonLord999
• 8,450 points
1,658 views
+2 votes
1 answer
0 votes
1 answer

How to use std::sort to sort an array in C++

We receive std::begin and std::end in C++0x/11, which are overloaded for arrays: #include <algorithm> int main(){ int v[2000]; ...READ MORE

answered Jun 1 in C++ by Damon
• 3,580 points
15 views
0 votes
1 answer

Declare abstract class in c++

An abstract class is one that is intended to be used as a base class .  At least one pure virtual function exists in an abstract class.  A pure virtual function is declared in the class declaration by using a pure specifier (= 0) in the declaration of a virtual member function. Here is an example of an abstract class: class AB { public: virtual void f() ...READ MORE

answered May 31 in C++ by Damon
• 3,580 points
20 views
webinar REGISTER FOR FREE WEBINAR X
Send OTP
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP