SortingAlgorithms/MergeSort.java at master · Cselwood/SortingAlgorithms · 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
import java.util.Arrays;

public class MergeSort {

    String complexity;

    MergeSort() {

        complexity = ". Quasilinear Time Complexity.";

    }

    void sort(int[] sortArray) {

        /*
        Begin Time Start
         */
        double start = (double) System.nanoTime();

        sort(sortArray, 0, sortArray.length - 1);

        /*
        End Time
         */
        double end = (double) System.nanoTime();

        System.out.println("MergeSort: " + Arrays.toString(sortArray) + complexity + " Seconds taken was " + ((end - start) / 1000000));

    }

    void sort(int[] sortArray, int first, int last) {

        if (first < last)
        {

            int m = (first + last)/2;

            sort(sortArray, first, m);
            sort(sortArray , m+1, last);
            mergeSort(sortArray, first, m, last);

        }

    }

    void mergeSort(int[] sortArray, int first, int middle, int last) {

        int firstHalf = middle - first + 1;
        int secondHalf = last - middle;

        int left[] = new int[firstHalf];
        int right[] = new int[secondHalf];

        for (int count = 0; count < firstHalf; count++) {

            left[count] = sortArray[first + count];

        }

        for (int countTwo = 0; countTwo < secondHalf; countTwo++) {

            right[countTwo] = sortArray[middle + 1 + countTwo];

        }

        int count = 0;
        int countTwo = 0;
        int countThree = first;

        while (count < firstHalf && countTwo < secondHalf)
        {

            if (left[count] <= right[countTwo])
            {

                sortArray[countThree] = left[count];
                count++;

            }
            else
            {

                sortArray[countThree] = right[countTwo];
                countTwo++;

            }

            countThree++;

        }

        while (count < firstHalf)
        {
            sortArray[countThree] = left[count];

            count++;
            countThree++;

        }

        while (countTwo < secondHalf)
        {
            sortArray[countThree] = right[countTwo];

            countTwo++;
            countThree++;

        }
    }
}