Practice-codes/msort.cpp at master · amnagrawal/Practice-codes · 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
#include<iostream>
#include<limits.h>
using namespace std;

int main()
{
	int a[10], i, k;
	void msort(int a[], int ini, int fin);
    cout<<"Enter 10 elements";
	for(i = 0; i<10; i++)
		cin>>a[i];

	cout<<"your array is:";
	for(i=0;i<10;i++)
		cout<<a[i]<<" ";

	cout<<"\n";

	msort(a, 0, 9);
	cout<<"\nthe sorted array is:";
	for(i=0; i<10; i++)
		cout<<a[i]<<" ";

	return 0;
}

void msort(int a[], int ini, int fin)
{
	void merge(int a[], int ini, int mid, int fin);
	int mid = (ini + fin)/2;
	if (ini<fin)
	{
		msort(a, ini, mid);
		msort(a, mid+1, fin);
		merge(a, ini, mid, fin);
	}
}

void merge(int a[], int ini=0, int mid=0, int fin=0)
{
	int i=0, j=0, k=0;
	int l1 = mid - ini + 2;
	int l2 = fin - mid +1;
	int l[l1], r[l2];

	l[l1-1] = r[l2 - 1] = INT_MAX;

	for(i=0;i<l1-1;i++)
	{
		l[i] = a[ini+i];
	}

	for(i=0; i<l2-1;i++)
	{
		r[i] = a[mid+i+1];
	}

	for(i=0, j=0, k=ini; k<=fin; k++)
	{
		if(l[i]<r[j])
		{
			a[k] = l[i];
			i++;
		}
		else
		{
			a[k] = r[j];
			j++;
		}
	}
}