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
• 4,720 points
30 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
• 4,760 points

Related Questions In C++

0 votes
0 answers

Selection sort in C++ (modified) not working for all cases

I was attempting to tweak the selection sort code in C++ in order to test the results.  My updated code is as follows: #include<bits/stdc++.h> using namespace std; int main() { ...READ MORE

Jun 29 in C++ by Damon
• 4,760 points
20 views
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
• 4,760 points
32 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
• 4,760 points
47 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
• 4,760 points
54 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,757 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
• 4,760 points
35 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
• 4,760 points
29 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