Online-coding-problems/Merge Sort at master · JaharshKotha/Online-coding-problems · 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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package summer;
import java.util.Scanner;

public class MSort {

	public static void main(String[] args)
	{
		System.out.print("Enter the length of the array :");

		Scanner in = new Scanner(System.in);
		int len= in.nextInt();
		int a[]= new int[len];

		for(int i=0;i<len;i++)
		{
		a[i]=(int)(Math.random()*100);

		}
		for(int i=0;i<len;i++)
		{
			System.out.print(a[i]+" ");

		}
		System.out.println(" ");
		a=Mergesort(a);

		for(int i=0;i<len;i++)
		{
			System.out.print(a[i]+" ");

		}


	}

	public static int [] Mergesort(int [] a)
	{
		int len=a.length;
		int mid=len/2;
		int ls=mid,rs=(len-mid);
		int b[]=new int[ls];
		int c[]=new int[rs];
		if(a.length==1)
		{
			return a;
		}

		for(int i=0;i<len;i++)
		{
			if(i<ls)
			{
				b[i]=a[i];
			}
			else
			{
				c[i-mid]=a[i];
			}
		}

		b=Mergesort(b);
		c=Mergesort(c);
		a=Merge(b,c);
		return a;

	}

	public static int [] Merge(int [] b, int [] c)
	{
		int len=b.length+c.length;
		int m[]=new int[len];
		int bc=0,cc=0,cnt=0;
		int i=0;
		for(i=0;i<len;i++)
		{
		if(bc == b.length)
		{
			cnt=1;
			break;
		}
		else if(cc== c.length)
		{
			cnt=2;
			break;
		}
		else
		{
			if(b[bc] > c[cc])
			{
				m[i]=c[cc];
				cc++;
			}
			else
			{
				m[i]=b[bc];
				bc++;
			}
		}

		}

		for(int j=i;j<len;j++)
		{
			if(cnt==1)
			{
				m[j]=c[cc];
				++cc;
			}
			else
			{
				m[j]=b[bc];
				++bc;
			}

		}

		cnt=0;
		return m;
	}


}