package com.company;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        ArrayList<Integer> a = new ArrayList<>();
        int[] stuff = {38, 27, 43, 3, 9, 82, 10};
        for (int i: stuff) { a.add(i); }
        mergeSort(a, 0, a.size()-1);

        printArray(a);
    }

    private static void printArray(ArrayList<Integer> a) {
        StringBuilder sb = new StringBuilder();
        for (int i : a) {
            sb.append(i);
            sb.append(", ");
        }
        sb.delete(sb.length()-2, sb.length());
        System.out.println(sb);
    }

    public static void mergeSort(ArrayList<Integer> array, int leftIndex, int rightIndex) {
        if (rightIndex > leftIndex) {
            int middleIndex = (rightIndex + leftIndex) / 2;
            mergeSort(array, leftIndex, middleIndex);
            mergeSort(array, middleIndex + 1, rightIndex);
            merge(array, leftIndex, middleIndex, rightIndex);
        }
    }

    private static void merge(ArrayList<Integer> array, int leftIndex, int middleIndex, int rightIndex) {
        // first subarraylist should be array[leftIndex..middleIndex]
        ArrayList<Integer> leftList = new ArrayList<>();
        for (int i = leftIndex; i <= middleIndex; i++) {
            leftList.add(array.get(i));
        }

        // second subarraylist should be array[middleIndex+1..rightIndex]
        ArrayList<Integer> rightList = new ArrayList<>();
        for (int i = middleIndex + 1; i <= rightIndex; i++) {
            rightList.add(array.get(i));
        }

        int i = leftIndex;
        int j = 0;
        int k = 0;

        while (j < leftList.size() && k < rightList.size()) {
            if (leftList.get(j) < rightList.get(k)) {
                array.set(i, leftList.get(j));
                j++;
            } else {
                array.set(i, rightList.get(k));
                k++;
            }
            i++;
        }
        while (leftList.size() > j) {
            array.set(i, leftList.get(j));
            i++;
            j++;
        }
        while (rightList.size() > k) {
            array.set(i, rightList.get(k));
            i++;
            k++;
        }
    }
}