Algorithm-Data-structure/Merge.java at main · luv-oct22/Algorithm-Data-structure · GitHub

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
package T1;

public class Merge extends SortAlgorithm{

    public void sort(Comparable[] objs){
        Comparable[] temp = new Comparable[objs.length];
        mergesort(objs,temp,0,objs.length-1);
    }

    public void mergesort(Comparable[] objs,Comparable[] temp,int left,int right){
        int mid = left + (right-left)/2;
        if(left == right) return;
        mergesort(objs,temp,left,mid);
        mergesort(objs,temp,mid+1,right);
        for(int i = left; i<=right;i++){
            temp[i] = objs[i];
        }

        int i1 = left;
        int i2 = mid + 1;
        for(int curr = left;curr<=right;curr++){
            if(i1 == mid+1){
                objs[curr] = temp[i2++];
            }
            else if(i2>right){
                objs[curr] = temp[i1++];
            }
            else if(less(temp[i1],temp[i2])){
                objs[curr] = temp[i1++];
            }
            else{
                objs[curr] = temp[i2++];
            }
        }
    }
}