Top Down / Bottom Up Merge Sort in Java

Maybe check out the description of the two methods first?

---

Timing Experiment Results Prediction

Bottom up method should perform better:

1. Top down method calls mergeSortHelper recursively, which will take O(logN) extra function call stack space

2. Top down method takes O(logN) extra time to break down the array into one / zero elements

But both of their space complexities are O(N) ( the temporary array to store sorted data )

Timing Experiment Results

Bottom up method sometimes performs slightly better than the top down one

The trend suggests that there is not that much a difference between the performance of the two methods

Some personal guess on why the gap between two methods is not that obvious:

• The data points I choose are not the best presentations
• My implementation is not the best practice
• The merge part takes so much time that it overshadows the breakdown process / extra call stack space
• The compiler did some optimization black magic under the hood

About the tests:

• Testing data set: randomly permuted Integer array list
• Testing data type: Integer
• Test data size: [0, 10k], step: 500
• Trails per data point: 10000

Top Down / Recursive Merge Sort

    /**
     * @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);
    }

Bottom Up / Iterative Merge Sort

    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));
        }
    }