forked from PrajaktaSathe/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.java
More file actions
74 lines (57 loc) · 2.01 KB
/
MergeSort.java
File metadata and controls
74 lines (57 loc) · 2.01 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
// Program that implements Merge sort
// Best case: O(nlogn)
// Average case: O(nlogn)
// Worst case: O(nlogn)
public class MergeSortMain {
static int arr[] = {100, 20, 15, 30, 5, 75, 40};
public static void main(String args[]) {
System.out.println("Array before sorting:");
printArray(arr, 0, arr.length - 1);
System.out.println("-----------------------------");
mergeSort(0, arr.length - 1);
System.out.println("-----------------------------");
System.out.println("Array After sorting:");
printArray(arr, 0, arr.length - 1);
}
public static void mergeSort(int start, int end) {
int mid = (start + end) / 2;
if (start < end) {
mergeSort(start, mid);
mergeSort(mid + 1, end);
merge(start, mid, end);
}
}
private static void merge(int start, int mid, int end) {
int[] tempArray = new int[arr.length];
int tempArrayIndex = start;
System.out.print("Before Merging: ");
printArray(arr, start, end);
int startIndex = start;
int midIndex = mid + 1;
while (startIndex <= mid && midIndex <= end) {
if (arr[startIndex] < arr[midIndex]) {
tempArray[tempArrayIndex++] = arr[startIndex++];
} else {
tempArray[tempArrayIndex++] = arr[midIndex++];
}
}
while (startIndex <= mid) {
tempArray[tempArrayIndex++] = arr[startIndex++];
}
while (midIndex <= end) {
tempArray[tempArrayIndex++] = arr[midIndex++];
}
for (int i = start; i <= end; i++) {
arr[i] = tempArray[i];
}
System.out.print("After merging: ");
printArray(tempArray, start, end);
System.out.println();
}
public static void printArray(int arr[], int start, int end) {
for (int i = start; i <= end; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}