forked from sPredictorX1708/Ultimate-Java-Resources
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.java
More file actions
70 lines (56 loc) · 1.41 KB
/
MergeSort.java
File metadata and controls
70 lines (56 loc) · 1.41 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
public class MergeSort{
void merge(int arr[], int start, int mid, int end){
int l = mid - start + 1;
int r = end - mid;
int LeftArray[] = new int [l];
int RightArray[] = new int [r];
for (int i=0; i<l; i++)
LeftArray[i] = arr[start + i];
for (int i=0; i<r; i++)
RightArray[i] = arr[mid + 1 + i];
int i = 0, j = 0;
int k = start;
while (i<l && j<r){
if (LeftArray[i] <= RightArray[j]){
arr[k] = LeftArray[i];
i++;
}
else{
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i<l){
arr[k] = LeftArray[i];
i++;
k++;
}
while (j<r){
arr[k] = RightArray[j];
j++;
k++;
}
}
void mergesort(int arr[], int start, int end){
if (start<end){
int mid = (start+end)/2;
mergesort(arr, start, mid);
mergesort(arr , mid+1, end);
merge(arr, start, mid, end);
}
}
public static void main(String args[]){
int arr[] = {10,4,6,3,2,1,9,5};
MergeSort test = new MyMergeSort();
test.mergesort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
for(int i=0; i<arr.length;i++){
System.out.println(arr[i] + " ");
}
}
}
//In Average case as well as in the Worst case using merge sort you will always
//get sorted array in O(nlogn) and in best case too the complexity is O(nlogn)
//because it follows divide and conquer method hence if it is for 2 elements
//or for 1M elements the time complexity will be always O(nlogn)