public class Sorter2
{
    public static void toString(int [] list)
    {
        for(int i = 0; i < list.length; i++)
        {
            System.out.print(list[i]);
            if(!(i + 1 == list.length))
            {
                System.out.print(",");
            }
        }

        System.out.println("");
    }

    public static void toString(int list[], int from, int to)
    {
        for(int i = from; i <= to; i++)
        {
            System.out.print(list[i]);
            if(i + 1 <= to)
            {
                System.out.print(",");
            }
        }

        System.out.println("");
    }


    public static void insertAt(int [] list, int insert_at, int taken_from)
    {
        int to_insert = list[taken_from];
        for(int i = taken_from; i >= insert_at; i--)
        {
            if(i != insert_at)
            {
                list[i] = list[i - 1];
            }
            else
            {
                list[i] = to_insert;
            }
        }
    }

    public static void sortSegments(int [] list ,int segment_one_begin, int midpoint, int segment_two_end)
    {
        toString(list, segment_one_begin, segment_two_end);

        int [] temp = new int[segment_two_end - segment_one_begin + 1];

        int counter_one = segment_one_begin;
        int counter_two = midpoint + 1;

        int i = 0;

        while(counter_one <= midpoint && counter_two <= segment_two_end)
        {
            if(list[counter_one] <= list[counter_two])
            {
                temp[i] = list[counter_one];
                counter_one++;
                i++;
            }
            else
            {
                temp[i] = list[counter_two];
                counter_two++;
                i++;
            }
        }

        while(i < temp.length && counter_one <= midpoint)
        {
            temp[i] = list[counter_one];
            counter_one++;
            i++;
        }

        while(i < temp.length && counter_two <= segment_two_end)
        {
            temp[i] = list[counter_one];
            counter_two++;
            i++;
        }

        for(int l = 0; l < temp.length; l++)
        {
            list[segment_one_begin + l] = temp[l];
        }

        toString(list, segment_one_begin, segment_two_end);
    }

    public static void mergeSort(int [] list, int segment_begining, int segment_end)
    {
        if(segment_begining < segment_end)
        {
            int midpoint = (segment_end + segment_begining) / 2;
            mergeSort(list, segment_begining, midpoint);
            mergeSort(list, midpoint + 1, segment_end);
            sortSegments(list, segment_begining, midpoint, segment_end);
        }

    }
    public static void mergeSort(int [] list)
    {
        mergeSort(list, 0, list.length - 1);
    }

    public static boolean isInOrder(int [] toCheck)
    {
        for(int i = 1; i < toCheck.length; i++)
        {
            if(toCheck[i] < toCheck[i - 1])
            {
                return false;
            }
        }

        return true;
    }

    public static int [] populate(int numOfItems)
    {
        int [] toReturn = new int[numOfItems];

        for(int i = 0; i < toReturn.length; i++)
        {
            toReturn[i] = (int) (Math.random() * 100 + 1);
        }

        return toReturn;
    }

    public static void main(String [] args)
    {
        int [] nums = populate(20);
        mergeSort(nums);
        toString(nums);
        System.out.println(isInOrder(nums));

    }
}