public class MergeSorterO {
    public static void sort(Comparable[] array) {
        sort(array,0,array.length);
    }
    public static void sort(Comparable[] array,int start,int end) {
        if(end-start < 2)
            return;

        int mid = start+(end-start)/2;
        sort(array,start,mid);
        sort(array,mid,end);


        Comparable[] first = new Comparable[mid-start];
        Comparable[] second = new Comparable[end-mid];
        for(int i=0;i<first.length;i++) {
            first[i] = array[i+start];
        }
        for(int i=0;i<second.length;i++) {
            second[i] = array[i+mid];
        }
        int i1 = 0, i2 = 0, i = start;
        while(i1 < first.length && i2 < second.length) {
            if(first[i1].compareTo(second[i2]) <= 0) {
                array[i] = first[i1];
                i1++;
                i++;
            } else {
                array[i] = second[i2];
                i2++;
                i++;
            }
        }
        while(i1 < first.length) {
            array[i] = first[i1];
            i1++;
            i++;
        }
        while(i2 < second.length) {
            array[i] = second[i2];
            i2++;
            i++;
        }
    }

    public static void main(String[] args) {
        var array = new Integer[]{3,5,2,7,100,4};
        MergeSorterO.sort(array);
        for(int i=0;i<array.length;i++)
            System.out.println(array[i]);
        var array2 = new String[]{"fish","ant","rice","people","bug","ham"};
        MergeSorterO.sort(array2);
        for(int i=0;i<array2.length;i++)
            System.out.println(array2[i]);
    }
}