/**
     * @return integer overflow prevention mid index getter
     */
    private static int getMiddleIndex(int start, int end) {
        return start + (end - start) / 2;
    }

    /**
     * merge two sorted array into a new sorted array
     */
    private static <T> void merge(ArrayList<T> data, int startLeft, int endLeft, int startRight, int endRight, Comparator<? super T> comparator, ArrayList<T> sortedResults) {
        int leftPointer = startLeft, rightPointer = startRight;
        int index = startLeft;
        while (leftPointer <= endLeft && rightPointer <= endRight) {
            T data1 = data.get(leftPointer);
            T data2 = data.get(rightPointer);
            if (comparator.compare(data1, data2) < 0) {
                sortedResults.set(index, data1);
                leftPointer++;
            } else {
                sortedResults.set(index, data2);
                rightPointer++;
            }
            index++;
        }
        while (leftPointer <= endLeft) {
            sortedResults.set(index, data.get(leftPointer));
            leftPointer++;
            index++;
        }
        while (rightPointer <= endRight) {
            sortedResults.set(index, data.get(rightPointer));
            rightPointer++;
            index++;
        }
        for (int i = startLeft; i <= endRight; i++) {
            data.set(i, sortedResults.get(i));
        }
    }

    /**
     * merge sort, time complexity: O(N*logN), space complexity: O(N)
     */
    private static <T> void mergeSortHelper(ArrayList<T> data, int start, int end, Comparator<? super T> comparator, ArrayList<T> sortedResults) {
        int dataSize = end - start + 1;

        if (dataSize < 2) {
            return;
        }

        int mid = getMiddleIndex(start, end);
        mergeSortHelper(data, start, mid, comparator, sortedResults);
        mergeSortHelper(data, mid + 1, end, comparator, sortedResults);
        merge(data, start, mid, mid + 1, end, comparator, sortedResults);
    }

    /**
     * call mergeSortHelper to do top down merge sort
     */
    public static <T> void topDownMergeSort(ArrayList<T> data, Comparator<? super T> comparator) {
        ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(data.size(), null));
        mergeSortHelper(data, 0, data.size() - 1, comparator, sortedResults);
    }

    public static <T> void bottomUpMergeSort(ArrayList<T> originalData, Comparator<? super T> comparator) {
        ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(originalData.size(), null));
        for (int sortingRange = 1; sortingRange < originalData.size(); sortingRange *= 2) {
            for (int left = 0; left < originalData.size(); left += 2 * sortingRange) {
                bottomUpMerge(originalData, sortedResults, left, sortingRange, comparator);
            }
            copyArray(sortedResults, originalData);
        }
    }

    private static <T> void bottomUpMerge(ArrayList<T> originalData, ArrayList<T> sortedResults, int start, int sortingRange, Comparator<? super T> comparator) {
        int right = Math.min(start + sortingRange, originalData.size());
        int end = Math.min(start + 2 * sortingRange, originalData.size());
        int leftPointer = start;
        int rightPointer = leftPointer + sortingRange;
        int index = start;
        while (leftPointer < right && rightPointer < end) {
            if (comparator.compare(originalData.get(leftPointer), originalData.get(rightPointer)) <= 0) {
                sortedResults.set(index, originalData.get(leftPointer));
                leftPointer++;
            } else {
                sortedResults.set(index, originalData.get(rightPointer));
                rightPointer++;
            }
            index++;
        }
        while (leftPointer < right) {
            sortedResults.set(index, originalData.get(leftPointer));
            leftPointer++;
            index++;
        }
        while (rightPointer < end) {
            sortedResults.set(index, originalData.get(rightPointer));
            rightPointer++;
            index++;
        }
    }

    /**
     * copy everything in the "from" array into "to" array
     */
    private static <T> void copyArray(ArrayList<T> from, ArrayList<T> to) {
        if (from.size() != to.size()) {
            throw new UnsupportedOperationException("From & to arrays have different sizes!");
        }
        for (int i = 0; i < from.size(); i++) {
            to.set(i, from.get(i));
        }
    }