-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.java
More file actions
98 lines (83 loc) · 2.48 KB
/
MergeSort.java
File metadata and controls
98 lines (83 loc) · 2.48 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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package algorithm.sorting;
/**
* The type Merge sort.
*/
public class MergeSort {
/**
* The Obj.
*/
static Helper obj = new Helper();
/**
* Merge sort.
*
* @param arr the arr
* @param leftIndex the left index
* @param rightIndex the right index
*/
public static void mergeSort(int[] arr, int leftIndex, int rightIndex){
if (leftIndex < 0 || rightIndex < 0)
return;
if (rightIndex > leftIndex) {
// Equivalent to (leftIndex+rightIndex)/2, but avoids overflow
int mid = leftIndex + (rightIndex - leftIndex) / 2;
// Sorting the first and second halves of the array
mergeSort(arr, leftIndex, mid);
mergeSort(arr, mid + 1, rightIndex);
// Merging the array
merge(arr, leftIndex, mid, rightIndex);
}
}
/**
* Merge.
*
* @param arr the arr
* @param left the left
* @param mid the mid
* @param right the right
*/
public static void merge(int arr[], int left, int mid, int right) {
int i,j,k;
int sizeLeft = mid - left + 1;
int sizeRight = right - mid;
// Initializing temporary arrays
int leftArr[] = new int[sizeLeft];
int rightArr[] = new int[sizeRight];
for( i=0;i<sizeLeft;i++)
leftArr[i]=arr[left+i];
for(j=0;j<sizeRight;j++)
rightArr[j]=arr[mid+1+j];
i=0;
j=0;
k=left;
// This is the main part of the algorithm
// Iterate over both arrays and copy the element that is smaller to the
// given array.
while(i<sizeLeft&&j<sizeRight){
if(leftArr[i]<=rightArr[j]){
arr[k++]=leftArr[i++];
}else{
arr[k++]=rightArr[j++];
}
}
// Copying the remaining elements of leftArr[], if there are any
while(i<sizeLeft){
arr[k++]=leftArr[i++];
}
// Copy the remaining elements of rightArr[], if there are any
while(j<sizeRight){
arr[k++]=rightArr[j++];
}
}
/**
* Main.
*
* @param args the args
*/
public static void main(String[] args){
int[] array = {2,5,1,7,9,45,0,12,69,-30,100,24,-9};
int arrSize=array.length;
obj.printArray(array, arrSize);
mergeSort(array,0,arrSize-1);
obj.printArray(array, arrSize);
}
}