11package Sorts ;
22
3- import static Sorts .SortUtils .print ;
4-
53/**
6- *This method implements the GenericMerge Sort
4+ * Genericmerge sort algorithm.
75 *
8- * @author Varun Upadhyay (https://github.com/varunu28)
9- * @author Podshivalov Nikita (https://github.com/nikitap492)
106 * @see SortAlgorithm
117 */
128class MergeSort implements SortAlgorithm {
139
1410/**
15- *This method implements the Generic Merge Sort
11+ *Generic merge sort algorithm implements.
1612 *
17- * @param unsorted the array which should be sorted
18- * @param <T> Comparable class
19- * @return sorted array
13+ * @param unsorted the array which should be sorted.
14+ * @param <T> Comparable class.
15+ * @return sorted array.
2016 */
2117@ Override
2218public <T extends Comparable <T >>T []sort (T []unsorted ) {
@@ -25,29 +21,30 @@ public <T extends Comparable<T>> T[] sort(T[] unsorted) {
2521 }
2622
2723/**
28- * @param arrThe array to be sorted
29- * @param leftThe first index of the array
30- * @param rightThe last index of the array Recursively sorts the array in increasing order
24+ * @param arrthe array to be sorted.
25+ * @param leftthe first index of the array.
26+ * @param rightthe last index of the array.
3127 */
3228private static <T extends Comparable <T >>void doSort (T []arr ,int left ,int right ) {
3329if (left <right ) {
34- int mid =left +( right - left ) / 2 ;
30+ int mid =( left +right ) >>> 1 ;
3531doSort (arr ,left ,mid );
3632doSort (arr ,mid +1 ,right );
3733merge (arr ,left ,mid ,right );
3834 }
3935 }
4036
4137/**
42- *This method implements the merge step ofthe merge sort
38+ *Merges two parts ofan array.
4339 *
44- * @param arrThe array to besorted
45- * @param leftThe first index of the array
46- * @param midThe middle index of the array
47- * @param rightThe last index of the array merges two parts of an array in increasing order
40+ * @param arrthe array to bemerged.
41+ * @param leftthe first index of the array.
42+ * @param midthe middle index of the array.
43+ * @param rightthe last index of the array merges two parts of an array in increasing order.
4844 */
4945private static <T extends Comparable <T >>void merge (T []arr ,int left ,int mid ,int right ) {
5046int length =right -left +1 ;
47+ @ SuppressWarnings ("unchecked" )
5148T []temp = (T [])new Comparable [length ];
5249int i =left ;
5350int j =mid +1 ;
@@ -72,21 +69,20 @@ private static <T extends Comparable<T>> void merge(T[] arr, int left, int mid,
7269System .arraycopy (temp ,0 ,arr ,left ,length );
7370 }
7471
75- // Driverprogram
72+ /** Drivercode */
7673public static void main (String []args ) {
74+ MergeSort mergeSort =new MergeSort ();
7775
78- // Integer Input
7976Integer []arr = {4 ,23 ,6 ,78 ,1 ,54 ,231 ,9 ,12 };
80- MergeSort mergeSort =new MergeSort ();
8177mergeSort .sort (arr );
78+ for (int i =0 ;i <arr .length -1 ; ++i ) {
79+ assert arr [i ] <=arr [i +1 ];
80+ }
8281
83- // Output => 1 4 6912235478231
84- print (arr );
85-
86- // String Inpu
8782String []stringArray = {"c" ,"a" ,"e" ,"b" ,"d" };
8883mergeSort .sort (stringArray );
89- // Output => abcde
90- print (stringArray );
84+ for (int i =0 ;i <stringArray .length -1 ; ++i ) {
85+ assert arr [i ].compareTo (arr [i +1 ]) <=0 ;
86+ }
9187 }
9288}
