Work With Unbalanced Merge Sort in Java Assignment Solution.

BS MERGE SORT

import java.util.Arrays;

import java.util.Random;

import java.util.stream.Collectors;

public class BSMergeSort implements IntegerSort {

    private int comparisons = 0;

    @Override

    public int[] sort(int[] arr) {

        BSTree.resetComparisons();

        int n = arr.length;

        BSTree[] trees = new BSTree[n];

        for (int i = 0; i

            trees[i] = new BSTree(arr[i]);

        }

        int last = n-1;

        while(last > 0) {

            BSTree lastTree = trees[last];

            BSTree preLastTree = trees[last-1];

            trees[last-1] = BSTree.mergeTrees(preLastTree, lastTree);

            last--;

        }

        comparisons = BSTree.getComparisons();

        return trees[0].getSorted();

    }

    @Override

    public int getComparisons() {

        return comparisons;

    }

}

BS TREE

public class BSTree {

    private static int comparisons = 0;

    public static int getComparisons() {

        return comparisons;

    }

    public static void resetComparisons() {

        comparisons = 0;

    }

    private Component root;

    public BSTree(int singleValue) {

        root = new Component(singleValue);

    }

    private BSTree(Component root) {

        this.root = root;

    }

    public int[] getSorted() {

        Component[] components = new Component[root.height];

        int componentsNum = 0;

        Component curr = root;

        while (curr != null) {

            components[componentsNum] = curr;

            curr = curr.right;

            componentsNum++;

        }

        componentsNum--;

        int[] currResult = null;

        while (componentsNum >= 0) {

            curr = components[componentsNum];

            int size = curr.leftTree == null ? 1 : curr.leftTree.length + 1;

            int[] step = new int[size];

            for (int i = 0; i

                step[i] = components[componentsNum].leftTree[i];

            }

            step[size-1] = curr.rootValue;

            if (currResult == null) {

                currResult = step;

            }

            else {

                int nextSize = step.length + currResult.length;

                int[] nextResult = new int[nextSize];

                int stepCounter = 0;

                int currResultCounter = 0;

                int counter = 0;

                while(counter < nextSize) {

                    if (stepCounter < step.length && currResultCounter < currResult.length) {

                        comparisons++;

                        if (step[stepCounter] <= currResult[currResultCounter]) {

                            nextResult[counter] = step[stepCounter];

                            stepCounter++;

                        }

                        else {

                            nextResult[counter] = currResult[currResultCounter];

                            currResultCounter++;

                        }

                    }

                    else if (stepCounter < step.length) {

                        nextResult[counter] = step[stepCounter];

                        stepCounter++;

                    }

                    else {

                        nextResult[counter] = currResult[currResultCounter];

                        currResultCounter++;

                    }

                    counter++;

                }

                currResult = nextResult;

            }

            componentsNum--;

        }

        return currResult;

    }

    public static BSTree mergeTrees(BSTree bsTree1, BSTree bsTree2) {

        Component[] tree1Components = new Component[bsTree1.root.height];

        int tree1ComponentsNum = 0;

        Component curr = bsTree1.root;

        while (curr != null) {

            tree1Components[tree1ComponentsNum] = curr;

            curr = curr.right;

            tree1ComponentsNum++;

        }

        tree1ComponentsNum--;

        Component[] tree2Components = new Component[bsTree2.root.height];

        int tree2ComponentsNum = 0;

        curr = bsTree2.root;

        while (curr != null) {

            tree2Components[tree2ComponentsNum] = curr;

            curr = curr.right;

            tree2ComponentsNum++;

        }

        tree2ComponentsNum--;

        Component carry = null;

        Component lastAdded = null;

        while(tree1ComponentsNum >= 0 || tree2ComponentsNum >= 0 || carry != null) {

            Component currComponent1 = tree1ComponentsNum >= 0 ? tree1Components[tree1ComponentsNum] : null;

            Component currComponent2 = tree2ComponentsNum >= 0 ? tree2Components[tree2ComponentsNum] : null;

            Component[] components = new Component[]{carry, currComponent1, currComponent2};

            int level = Integer.MAX_VALUE;

            for (Component c : components) {

                if (c != null) {

                    if (level > c.height) {

                        level = c.height;

                    }

                }

            }

            Component[] levelComponents = new Component[3];

            int levelComponentsNum = 0;

            for (Component c : components) {

                if (c != null) {

                    if (level == c.height) {

                        if (c == currComponent1) {

                            tree1ComponentsNum--;

                        }

                        if (c == currComponent2) {

                            tree2ComponentsNum--;

                        }

                        levelComponents[levelComponentsNum] = c;

                        levelComponentsNum++;

                    }

                }

            }

            if (levelComponentsNum == 3) {

                int maxIndex = 0;

                int maxRoot = levelComponents[0].rootValue;

                for (int i = 1; i

                    Component c = levelComponents[i];

                    comparisons++;

                    if (c.rootValue > maxRoot) {

                        maxIndex = i;

                        maxRoot = c.rootValue;

                    }

                }

                Component[] toMerge = new Component[2];

                int toMergeNum = 0;

                for (int i = 0; i

                    if (i != maxIndex) {

                        toMerge[toMergeNum] = levelComponents[i];

                        toMergeNum++;

                    }

                }

                levelComponents[maxIndex].right = lastAdded;

                lastAdded = levelComponents[maxIndex];

                carry = mergeComponents(toMerge[0], toMerge[1]);

            }

            else if (levelComponentsNum == 2){

                carry = mergeComponents(levelComponents[0], levelComponents[1]);

            }

            else if (levelComponentsNum == 1) {

                levelComponents[0].right = lastAdded;

                lastAdded = levelComponents[0];

                carry = null;

            }

        }

        return new BSTree(lastAdded);

    }

    private static class Component {

        int height;

        int rootValue;

        int[] leftTree;

        Component right;

        Component(int rootValue) {

            this.rootValue = rootValue;

            this.height = 1;

            this.leftTree = null;

            this.right = null;

        }

        Component(int rootValue, int[] leftTree) {

            this.rootValue = rootValue;

            int size = leftTree.length;

            this.height = 1;

            while(size > 0) {

                size /= 2;

                height++;

            }

            this.leftTree = leftTree;

            this.right = null;

        }

    }

    private static Component mergeComponents(Component c1, Component c2) {

        if (c1.height != c2.height) {

            throw new IllegalStateException();

        }

        int size = c1.leftTree == null ? 1 : c1.leftTree.length + 1;

        int newLength = 2 * size - 1;

        int[] leftTree = new int[newLength];

        int counter1 = 0;

        int counter2 = 0;

        int counter = 0;

        while(counter < newLength) {

            if (counter1 < size && counter2 < size) {

                int val1 = (counter1 < size - 1) ? c1.leftTree[counter1] : c1.rootValue;

                int val2 = (counter2 < size - 1) ? c2.leftTree[counter2] : c2.rootValue;

                comparisons++;

                if (val1 <= val2) {

                    leftTree[counter] = val1;

                    counter1++;

                }

                else {

                    leftTree[counter] = val2;

                    counter2++;

                }

            }

            else if (counter1 < size) {

                leftTree[counter] = (counter1 < size - 1) ? c1.leftTree[counter1] : c1.rootValue;

                counter1++;

            }

            else {

                leftTree[counter] = (counter2 < size - 1) ? c2.leftTree[counter2] : c2.rootValue;

                counter2++;

            }

            counter++;

        }

        int rootValue = (counter1 < size) ? c1.rootValue : c2.rootValue;

        return new Component(rootValue, leftTree);

    }

    public static void main(String[] args) {

        Component c1 = new Component(90, new int[]{21, 30, 89});

        Component c11 = new Component(77);

        c1.right = c11;

        Component c2 = new Component(93, new int[]{3, 22, 57});

        Component c21 = new Component(87, new int[]{8});

        Component c211 = new Component(58);

        c21.right = c211;

        c2.right = c21;

        BSTree tree1 = new BSTree(c1);

        BSTree tree2 = new BSTree(c2);

        BSTree tree = mergeTrees(tree1, tree2);

        System.out.println(tree);

    }

}

INTEGER SORT

public interface IntegerSort {

    int[] sort(int[] arr);

    int getComparisons();

}

MERGE SORT

public class MergeSort implements IntegerSort {

    private int comparisons = 0;

    @Override

    public int[] sort(int[] arr) {

        comparisons = 0;

        int[] aux = new int[arr.length];

        int[] copy = new int[arr.length];

        System.arraycopy(arr, 0, copy, 0, arr.length);

        mergeSort(copy, aux, 0, arr.length - 1);

        return copy;

    }

    @Override

    public int getComparisons() {

        return comparisons;

    }

    private void mergeSort(int[] arr, int[] aux, int low, int high) {

        if (low >= high) {

            return;

        }

        int middle = (low + high) / 2;

        mergeSort(arr, aux, low, middle);

        mergeSort(arr, aux, middle+1, high);

        merge(arr, aux, low, middle, high);

    }

    private void merge(int[] arr, int[] aux, int low, int mid, int high) {

        if (high + 1 - low >= 0) System.arraycopy(arr, low, aux, low, high + 1 - low);

        int i = low;

        int j = mid + 1;

        for (int k = low; k <= high; k++) {

            if (i > mid) {

                arr[k] = aux[j];

                j++;

            } else if (j > high) {

                arr[k] = aux[i];

                i++;

            } else {

                comparisons++;

                if (aux[i] <= aux[j]) {

                    arr[k] = aux[i];

                    i++;

                } else {

                    arr[k] = aux[j];

                    j++;

                }

            }

        }

    }

}