DSA 2

import java.util.Arrays;
//Gorozhankin Egor BS19-01

// out-of-place
// stable in every situation O(n log n)

public class MergeSort<T> implements Comparable<T> { // O(n log n)
    public static <T> T[] mergeSort(T[] array) {
        return mergeSort(array, 0, array.length - 1);
    }


    @SuppressWarnings("unchecked")
    public static <T> T[] mergeSort(T[] array, int left, int right) {
        if (left == right)
            return array;

        int mid = (left + right) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);

        int i = left, j = mid + 1;
        T[] sorted = (T[]) new Object[right - left + 1];

        for (int k = 0; k < sorted.length; k++) {
            if (i > mid || (j <= right && ((Comparable<T>) array[i]).compareTo(array[j]) > 0))
                sorted[k] = array[j++];
            else
                sorted[k] = array[i++];
        }

        for (int k = 0; k < sorted.length; k++)
            array[k + left] = sorted[k];

        return array;
    }

    @Override
    public int compareTo(T o) {
        return this.compareTo(o);
    }
}