-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathMergeSort.java
More file actions
52 lines (46 loc) · 1.37 KB
/
Copy pathMergeSort.java
File metadata and controls
52 lines (46 loc) · 1.37 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
package Array;
/**
* Created by Prashant on 6/11/16.
* merge sort is divide and conquer + combine approach. it's complexity is O(nlgn)
* java pass by value or reference? : https://www.youtube.com/watch?v=hNR6fsksEu8
* array pass by value or reference? : http://stackoverflow.com/questions/1610757/pass-array-to-method-java
* TODO: read: http://www.yoda.arachsys.com/java/passing.html
*/
public class mergeSort {
public static void mergeSort(int[] a, int l, int r) {
if(l<r) {
int mid = (l+r)/2;
mergeSort(a, l, mid);
mergeSort(a, mid+1, r);
merge(a, l, mid, r);
}
}
public static void merge(int[] a, int l, int mid, int r) {
int[] tmp = new int[r-l+1];
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r) {
if(a[i]<=a[j]) {
tmp[k++]=a[i++];
} else {
tmp[k++]=a[j++];
}
}
while(i<=mid) {
tmp[k++] = a[i++];
}
while(j<=r) {
tmp[k++] = a[j++];
}
for(i=0;i<tmp.length;i++) {
a[l++] = tmp[i];
}
}
public static void main(String[] args) {
int[] a = {10,9,8,7,6,5,4,3,2,1};
mergeSort(a, 0, 9);
for(int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
}
System.out.print(" ");
}
}