package com.company;

import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    public static void printPreSorted(ArrayList<ArrayList<Integer>> toPrint) {
        System.out.println();
        for (int i = 0; i < toPrint.size(); i++) {
            System.out.print(Arrays.toString(toPrint.get(i).toArray()));
        }
    }

    public static int[] mergeSort(int[] toSort) {
        ArrayList<ArrayList<Integer>> listOfParts = new ArrayList<>();
        ArrayList<Integer> part = new ArrayList<>();
        for (int i = 0; i < toSort.length; i++) {
            if (part.size() == 0 || part.get(part.size() - 1) < toSort[i]) {
                part.add(toSort[i]);
            } else {
                listOfParts.add(part);
                part = new ArrayList<>();
                part.add(toSort[i]);
            }
        }
        listOfParts.add(part);
        while (listOfParts.size() > 1) {
            printPreSorted(listOfParts);
            ArrayList<Integer> newPart = new ArrayList<>();
            int newPartLength = listOfParts.get(0).size() + listOfParts.get(1).size();
            for (int i = 0; i < newPartLength; i++) {
                if (listOfParts.get(1).size() == 0 || (listOfParts.get(0).size() > 0 && listOfParts.get(0).get(0) < listOfParts.get(1).get(0))) {
                    newPart.add(listOfParts.get(0).get(0));
                    listOfParts.get(0).remove(0);
                } else {
                    newPart.add(listOfParts.get(1).get(0));
                    listOfParts.get(1).remove(0);
                }
            }
            listOfParts.remove(0);
            listOfParts.set(0, newPart);
        }
        printPreSorted(listOfParts);
        int[] sortedArray = new int[listOfParts.get(0).size()];
        for (int i = 0; i < listOfParts.get(0).size(); i++) {
            sortedArray[i] = listOfParts.get(0).get(i);
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        int[] a = new int[]{4, 3, 5335, 87, 23, 464, 78965, 32, 311, 5, 35, 5, 1};
        a = mergeSort(a);
    }

}