# Work With Unbalanced Merge Sort in Java Assignment Solution.

June 29, 2024
Dr. Marlowe
🇬🇧 United Kingdom
Java
Dr. Marlowe Emberly is a trailblazer in the field of computer science, having earned her PhD from the University of Cambridge, UK, renowned for its excellence in research and academia. With eight years of experience in the industry, Marlowe has completed over 800 Java Homework assignments with unparalleled dedication and expertise.
Key Topics
• Instructions
• Requirements and Specifications
Tip of the day
News

## Instructions

Objective
Write a java assignment program to work with unbalanced merge sort.

## Requirements and Specifications

Source Code

`BS MERGE SORTimport 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 TREEpublic 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 SORTpublic interface IntegerSort {    int[] sort(int[] arr);    int getComparisons();}MERGE SORTpublic 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++;                }            }        }    }}`

## Related Samples

Check out our Java Assignments sample section, where you'll find meticulously crafted solutions to programming challenges. From basic principles to advanced algorithms, each sample includes clear, commented code for learning and reference. Ideal for students aiming to enhance their Java proficiency and excel in programming assignments. Start exploring Java mastery with our curated samples today!