GitHub Viewer
package Sorts;
import static Sorts.SortUtils.print;
/**
* This method implements the Generic Merge Sort
*
* @author Varun Upadhyay (https://github.com/varunu28)
* @author Podshivalov Nikita (https://github.com/nikitap492)
* @see SortAlgorithm
*/
class MergeSort implements SortAlgorithm {
/**
* This method implements the Generic Merge Sort
*
* @param unsorted the array which should be sorted
* @param Comparable class
* @return sorted array
*/
@Override
public T[] sort(T[] unsorted) {
doSort(unsorted, 0, unsorted.length - 1);
return unsorted;
}
/**
* @param arr The array to be sorted
* @param left The first index of the array
* @param right The last index of the array Recursively sorts the array in increasing order
*/
private static void doSort(T[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
doSort(arr, left, mid);
doSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
/**
* This method implements the merge step of the merge sort
*
* @param arr The array to be sorted
* @param left The first index of the array
* @param mid The middle index of the array
* @param right The last index of the array merges two parts of an array in increasing order
*/
private static void merge(T[] arr, int left, int mid, int right) {
int length = right - left + 1;
T[] temp = (T[]) new Comparable[length];
int i = left;
int j = mid + 1;
int k = 0;
while (i