Question

Language: Java

Implement Merge Sort

Answer 1

import java.util.Arrays;

public class MergeSort {
    /**
     * Recursive helper method for merging arr[l..m] and arr[m+1..r]
     *
     * @param arr
     * @param l
     * @param m
     * @param r
     */
    static void merge(double[] arr, int l, int m, int r) {
        double[] first = new double[m - l + 1];
        double[] second = new double[r - m];
        // copy array arr[l..m] into first
        for (int i = 0; i < first.length; i++)
            first[i] = arr[l + i];
        // copy array arr[m+1..r] into second
        for (int i = 0; i < second.length; i++)
            second[i] = arr[m + 1 + i];
        int ind1 = 0, ind2 = 0, i = l;
        // merge first and second arrays into arr[l..r]
        while (ind1 < first.length || ind2 < second.length) {
            if (ind2 >= second.length || (ind1 < first.length && first[ind1] < second[ind2])) {
                arr[i++] = first[ind1++];
            } else if (ind1 >= first.length || second[ind2] < first[ind1]) {
                arr[i++] = second[ind2++];
            }
        }
    }

    /**
     * Recursive merge sortArray helper method
     *
     * @param arr
     * @param l
     * @param r
     */
    static void mergeSort(double[] arr, int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // SortAll first and second halves
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /**
     * merge sortArray method with the normal array input parameter
     *
     * @param arr
     */
    static void mergeSort(double[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        double[] arr = {0.1, 5, 10.5, 9.8, 3.3, 5.6, 8.5, 7.3, 1.5, 99.9, 30};
        System.out.println("Original array: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}