vtu_lab_programs/msort.java at master · Dippokey/vtu_lab_programs · 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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.io.*;
import java.util.*;


class msort{

    void divide(int arr[], int l, int r){

        if (l<r){
            int m = (l+r)/2;
            divide(arr, l, m);
            divide(arr, m+1, r);
            merge(arr, l, m, r);


        }

    }

    void merge(int arr[], int l, int m, int r){

        //initializaiton
        int n1 = m-l+1;
        int n2 = r-m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        //filling the array
        for(int i=0; i<n1; i++){
            L[i] = arr[i+l];

        }
        for(int j=0; j<n2; j++){
            R[j] = arr[j+m+1];
        }

        int i=0, j=0, k=l;

        while (i<n1 && j<n2){

            if (L[i]<=R[j]){
                arr[k] = L[i];
                k++;
                i++;

            }
            else{
                arr[k] = R[j];
                k++;
                j++;

            }
        }
        while (i<n1){
            arr[k] = L[i];
            k++;
            i++;
        }
        while (j<n2){
            arr[k] = R[j];
            j++;
            k++;
        }

    }

    public void display(int arr[], int n){
        int i;
        for(i=0; i<n; i++){
            System.out.println(arr[i]);
        }
    }


    public static void main(String[] args) {

        int n, i;
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of elements");
        n = sc.nextInt();

        int arr[] = new int[n];

        Random r = new Random();

        for(i=0; i<n; i++){
            arr[i] = r.nextInt(n);
        }

        msort obj = new msort();

        System.out.println("the array is:");
        obj.display(arr, n);

        //time calculation
        long startTime = System.nanoTime();

        obj.divide(arr, 0, n-1);


        long endTime = System.nanoTime();


        System.out.println("the sorted array is:");
        obj.display(arr, n);

        double elapse = endTime-startTime;
        double time = elapse/1000000;

        System.out.println("the time taken is "+time  );

    }
}