mjhjmtu

This is a code uses mergesort algorithm to sort a list of elements.What are the possible improvements on the code?Also are there any unhealthy coding practice involved in this code?

#include<iostream>
#include<vector>
#include<random>
#include<chrono>
using namespace std;
using namespace std::chrono;
vector<int> merge(vector<int> a,vector<int> b)
 int i=0;
 int j=0;
 vector<int> result;
 while(i<a.size()&&j<b.size())
 if(a[i]<b[j])
 result.push_back(a[i]);
 i++;
 
 else
 result.push_back(b[j]);
 j++;
 
 
 while(i<a.size())
 result.push_back(a[i]);
 i++;
 
 while(j<b.size())
 result.push_back(b[j]);
 j++;
 
 return result;


vector<int> mergesort(vector<int> a,int low,int hi)
 vector<int> b,c,result;
 if(low==hi)
 return a[hi];
 b=mergesort(a,low,(low+hi)/2);
 c=mergesort(a,(hi+low)/2+1,hi);
 result=merge(b,c);
 return result;

int main()

 std::random_device rd; // obtain a random number from hardware
 std::mt19937 eng(rd()); // seed the generator
 std::uniform_int_distribution<> distr(0,90); // define the range
 vector <int> num;
 for(int i=0;i<30;i++)
 num.push_back(distr(eng)); 
 vector<int> a=mergesort(num,0,num.size()-1);
 for(auto &i:a)
 cout<<i<<" "; 

#include<iostream>
#include<vector>
#include<random>
#include<chrono>

Leave some space between the #includes and the rest of your code, that's easier to read. Besides, I really like <chrono> myself too, but you don't seem to use it afterwards.

using namespace std;
using namespace std::chrono;

using directives for a whole namespace is a bad idea. You risk conflicts between the names defined in std (and there's quite a lot of them) and those you define yourself. Safety is worth a few more keystrokes.

vector<int> merge(vector<int> a,vector<int> b)

That function signature means you're passing a and b by value, that is to say you copy the argument vectors. It might be the good move sometimes, but here it isn't, because you only read them. So const std::vector<int>& a, const std::vector<int>& b is better.

 int i=0;
 int j=0;

i, j, why not? but it doesn't scream what you'll be using those variables for.

 vector<int> result;
 while(i<a.size()&&j<b.size())

I would rather use iterators in the first place (I mean, in the function's signature), because:

• it avoids comparison issues (vector.size() is unsigned, whereas i and j are signed)


• it makes it easier to write and use generic code


• 
  

  it allows you to merge sequences which are only a part of a container, or even inside the same container.

  
  
  

  if(a[i]<b[j])
  

  
  

There's a trick here: if a[i] == b[j] you'll insert b[j] first. It might be innocuous -it is for an int- but programmers expect that min(a, b) will return a if a == b. Since a sorting algorithm is a good candidate for abstraction (a vector of strings is sorted the same way as a vector of ints or floats), you should respect that rule.

 result.push_back(a[i]);
 i++;

Unless you need to keep track of the old value, use pre-incrementation (++i) since i++ creates and returns a temporary value.

 
 else
 result.push_back(b[j]);
 j++;
 
 
 while(i<a.size())
 result.push_back(a[i]);
 i++;
 
 while(j<b.size())
 result.push_back(b[j]);
 j++;
 

copy and paste is an anti-pattern. Standard algorithms will provide what you need in a more elegant way, especially if you use iterators: std::copy(current_a, a.end(), std::back_inserter(result));

 return result;


vector<int> mergesort(vector<int> a,int low,int hi)
 vector<int> b,c,result;
 if(low==hi)
 return a[hi];
 b=mergesort(a,low,(low+hi)/2);
 c=mergesort(a,(hi+low)/2+1,hi);
 result=merge(b,c);
 return result;

This part is all right, even if I believe you should try to reduce the place you need to merge-sort or at least the number of allocations.

int main()

 std::random_device rd; // obtain a random number from hardware
 std::mt19937 eng(rd()); // seed the generator
 std::uniform_int_distribution<> distr(0,90); // define the range
 vector <int> num;
 for(int i=0;i<30;i++)
 num.push_back(distr(eng)); 
 vector<int> a=mergesort(num,0,num.size()-1);
 for(auto &i:a)

You generally don't take integers by reference (a reference is the size of or bigger than an int, and you don't take non-const references when you don't modify the variable, which you don't.

 cout<<i<<" "; 

The functions should be templatized so that they can sort any kind of comparable values.

You have made the two classic mistakes in mergesort:

• 
  

  Unstable sorting.

  
  
  

  
  

  if(a[i]<b[j])
   result.push_back(a[i]);
   i++;
  
  else
   result.push_back(b[j]);
   j++;
  
  

  
  

  
  
  

  One of the useful properties of mergesort is that it is a stable sorting algorithm. To achieve that, though, when two a[i] and b[j] are equal, you have to prefer to take the item from a first, because a was originally to the left of b. Therefore, use <= for that comparison.

  
  
  

  Of course, stability doesn't matter when sorting integers. But you might as well write it correctly so that it also works for sorting arbitrary objects.

  
  


• 
  

  Overflow.

  
  
  

  
  

  b=mergesort(a,low,(low+hi)/2);
  c=mergesort(a,(hi+low)/2+1,hi);
  

  
  

  
  
  

  low+high is vulnerable to integer overflow. The better technique would be low + (high - low) / 2.

  
  

Merge Sort is a great choice when the data don't fit into working memory. However, our inputs and outputs are all in memory, so we're better off using a more suitable algorithm, such as Quicksort.

Luckily, the C++ Standard Library provides std::sort(), which is intended to be a good choice when inputs fit into memory (it's the implementer's choice of algorithm, not necessarily Quicksort). A good implementation won't require such a large memory overhead as the hand-written sort (we need space for the entire input and output during the sort - i.e. twice that of the elements, leading to an increased risk of std::bad_alloc; most std::sort() require little or no extra memory during operation).

Summary: use std::sort() and save your brainpower for other challenges.