iframe-proxy | Sunbelt Computer Software

64 lines (53 loc) · 2.09 KB

package sorting;
import java.util.Arrays;
public class MergeSortApp {
    //Time complexity: O(N * logN)
    //Space complexity: O(N)
    private static class MergeSort {
        private int[] array;
        public void mergeSort(int[] arr) {
            array = arr;
            int len = array.length;
            int[] workspace = new int[len];
            recursiveMergeSort(workspace, 0, len - 1);
        private void recursiveMergeSort(int[] workSpace, int lowerBound,
                                        int upperBound) {
            if (lowerBound == upperBound) {
                return;
            } else {
                int mid = (lowerBound + upperBound) / 2;
                recursiveMergeSort(workSpace, lowerBound, mid);
                recursiveMergeSort(workSpace, mid + 1, upperBound);
                merge(workSpace, lowerBound, mid + 1, upperBound);
        private void merge(int[] workspace, int lowPointer,
                           int highPointer, int upperBound) {
            int i = 0;
            int lowerBound = lowPointer;
            int mid = highPointer - 1;
            int numberOfItems = upperBound - lowerBound + 1;
            while (lowPointer <= mid && highPointer <= upperBound) {
                if (array[lowPointer] < array[highPointer]) {
                    workspace[i++] = array[lowPointer++];
                } else {
                    workspace[i++] = array[highPointer++];
            while (lowPointer <= mid)
                workspace[i++] = array[lowPointer++];
            while (highPointer <= upperBound)
                workspace[i++] = array[highPointer++];
            for (i = 0; i < numberOfItems; i++)
                array[lowerBound + i] = workspace[i];
    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] arr = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
        System.out.println("Before: " + Arrays.toString(arr));
        mergeSort.mergeSort(arr);
        System.out.println("After: " + Arrays.toString(arr));

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

MergeSortApp.java

Latest commit

History

MergeSortApp.java

File metadata and controls