DataStructures/MergeSort.cpp at master · Kapil-Vermani/DataStructures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Merge Sort in c++
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;

void merge(std::vector<int>& a,int s,int e)
{
      std::vector<int> temp(e-s+1);
      auto mid = (s+e)/2;
      auto i = s;
      auto j =  mid+1;
      auto  k = 0;
      while( (i<=mid) && (j<=e))
      {
         if(a[i] <= a[j])
         {
            temp[k++] = a[i++];
         }
         else
         {
           temp[k++] = a[j++];
         }
      }
      while(i<=mid)
      {
            temp[k++]=a[i++];
      }
      while(j<=e)
      {
          temp[k++]=a[j++];
      }
      auto idx = 0;
      for(int cntr=s;cntr<=e;cntr++)
      {
          a[cntr] = temp[idx++];
      }
}
void mergesort(std::vector<int>& a,int s,int e)
{
     if((e-s) <= 0)
     {
    	 return;
     }
     //divide
     int mid = (s+e)/2;
     //sort
     mergesort(a,s,mid);
     mergesort(a,mid+1,e);
     //merge
     merge(a,s,e);
}
int main() {
	srand(time(0));
	auto generated_rand_number = rand() % 20;
    while (generated_rand_number <=0)
    {
       generated_rand_number = rand()%20;
    }
	vector<int> input_vec(generated_rand_number);
	srand(time(0));
    for(int i=0;i<generated_rand_number;i++)
	{
		auto temp = rand();
        input_vec[i] = temp;
	}
    std::cout<<"Array before sorting ...."<<std::endl;
    for(int i=0;i<input_vec.size();i++)
    {
        std::cout<<input_vec[i]<<"\t";
    }
    std::cout<<std::endl;
	mergesort(input_vec,0,generated_rand_number-1);
    std::cout<<"Array after sorting... "<<std::endl;
    for(int i=0;i<input_vec.size();i++)
    {
        std::cout<<input_vec[i]<<"\t";
    }
	return 0;
}