import java.util.Arrays;

public class MergingSort {

    public static void main(String[] args) {
        int[] array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};

        System.out.println("Before: " + Arrays.toString(array));
        sort(array);
        System.out.println("After:  " + Arrays.toString(array));
    }

    public static int[] sort(int[] arr) {
        int[] ans = recurse(arr, 0, arr.length - 1);

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

        return ans;
    }

    private static int[] recurse(int[] arr, int start, int end) {
        // start is the head index, end is the tail index

        int len = end - start + 1;

        // no need to split
        if (len == 1) {
            // FIXME Do not return arr, instantiate a new array of length 1 to hold the single element.
            return new int[]{arr[start]};
        }

        // split the given array until the length becomes 1
        // start=1, end=2, mid=1
        int mid = (start + end) / 2;

        // [1,1]
        int[] left = recurse(arr, start, mid);

        // [2,2]
        int[] right = recurse(arr, mid + 1, end);

        return merge(left, right);
    }

    private static int[] merge(int[] arr1, int[] arr2) {
        int len1 = arr1.length;
        int len2 = arr2.length;

        int i = 0;
        int j = 0;
        int k = 0;

        int[] result = new int[len1 + len2];

        while (i < len1 && j < len2) {
            if (arr1[i] <= arr2[j]) {
                result[k++] = arr1[i++];
            } else {
                result[k++] = arr2[j++];
            }
        }

        while (i < len1) {
            result[k++] = arr1[i++];
        }

        while (j < len2) {
            result[k++] = arr2[j++];
        }

        return result;
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-07 09:22:21

results matching ""

    No results matching ""