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, 2022 in C++ by Nicholas
• 7,760 points
447 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, 2022 by Damon
• 4,960 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, 2022 in C++ by Damon
• 4,960 points
285 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, 2022 in C++ by Damon
• 4,960 points
595 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, 2022 in C++ by Damon
• 4,960 points
969 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, 2022 in C++ by Damon
• 4,960 points
562 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
3,458 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, 2022 in C++ by Damon
• 4,960 points
852 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, 2022 in C++ by Damon
• 4,960 points
359 views
webinar REGISTER FOR FREE WEBINAR X
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP