forked from Asiatik/codezilla
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.java
More file actions
77 lines (74 loc) · 2.44 KB
/
Copy pathMergeSort.java
File metadata and controls
77 lines (74 loc) · 2.44 KB
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
public class MergeSort {
/*
This function takes an array to be sorted,
divide the array in two sub arrays i.e leftSubArray and RightSubarray if size of array is greater than 1
then recursivelly call sort for subarrays
and then call the merge function
*/
public void sort(int[] arr)
{
if (arr.length>1)
{
int mid=(arr.length)/2;
int sizel=mid; // size for left sub array
int sizer=arr.length-mid; // size for right sub array
int[] larr=new int[sizel]; // left sub array
int[] rarr=new int[sizer]; // right sub array
int t=0;
for (int i=0;i<mid;i++,t++) // copies elements in left sub array
{
larr[i]=arr[t];
}
for (int i=0;i<sizer;i++,t++) // copies elements in right sub array
{
rarr[i]=arr[t];
}
sort(larr); // recursively call sort funtion for left sub array
sort(rarr); // recursively call sort function for right sub array
merge(larr,rarr,arr); // call merge funtion to merge the sub arrays in array
}
}
/*
this function takes three arrays two subarray to be merged in third array in sorted form
*/
private void merge(int[] larr,int[] rarr,int[] arr)
{
int lsize=larr.length; // size of left sub array
int rsize=rarr.length; // size of right sub array
int l=0,r=0,a=0; // l for left sub array index, r for right sub array index, a for array index
while (l<lsize && r<rsize) // coping elements in array
{
if (larr[l]<rarr[r])
{
arr[a]=larr[l];
l++;a++;
}
else
{
arr[a]=rarr[r];
r++;a++;
}
}
while (l<lsize) // coping remaing elements of left sub array in array
{
arr[a]=larr[l];
l++;a++;
}
while (r<rsize) // coping remaining elements of right sub array in array
{
arr[a]=rarr[r];
r++;a++;
}
}
// driver function
public static void main(String args[])
{
int arr[] = {10,2,4,9,100,80,70};
System.out.println("Given Array");
System.out.print(Arrays.toString(arr));
MergeSort ob = new MergeSort();
ob.sort(arr);
System.out.println("\nSorted array");
System.out.print(Arrays.toString(arr));
}
}