Question

write a java merge sort called MERGE-SORT-A(), Using recursive calls and NO INSERTION-SORT() as a sub-procedure.

Answer 1

public class MergeSort

{

    public static void merge_sort(long[] arr,int p, int r)

    {

        // if index is right

        if(p < r)

        {

            // get the mid index

            int mid = (p + r) / 2;

           

            // sort the left subarray

            merge_sort(arr, p, mid);

           

            // sort the right subarray

            merge_sort(arr, mid + 1, r);

           

            // merge the two subarrays

            merge(arr, p, mid, r);

        }

    }

   

    // merge thw two arrays

    public static void merge(long[] arr,int p,int q,int r)

    {

        // get the length of left subarray

        int n1 = q - p + 1;

       

        // get the length of right subarray

        int n2 = r - q;

       

        int i,j,k;

       

        // create two arrays left and right

        long[] left = new long[n1 + 1];

        long[] right = new long[n2 + 1];

        // fill left with the contents of left subarray of arr

        for(i = 0; i < n1; i++)

            left[i] = arr[p + i];

       

        // fill right with the contents of right subarray of arr

        for(i = 0; i < n2; i++)

            right[i] = arr[q + i + 1];

       

        // set the last element to infinity

        left[n1] = Long.MAX_VALUE;

        right[n2] = Long.MAX_VALUE;

       

        i=0;

        j=0;

       

        for(k = p ; k <= r; k++)

        {

            // if the current element of left is smaller than

            // current element of right

            if(left[i] <= right[j])

            {

                arr[k] = left[i];

                i++;

            }

            // if the current element of left is larger than

            // current element of right

            else

            {

                arr[k] = right[j];

                j++;

            }

        }

    }

   

    // display the array

    public static void display(long arr[])

    {

        int i;

       

        // iterate through the array

        for (i = 0; i< arr.length; i++)

            System.out.print(arr[i] + " ");

       

        System.out.println();

    }

   

    public static void main(String[] args)

    {

        int maxSize = 20;

       

        // initialize the array

        long[] a = new long[maxSize];

       

        // fill the array with random elements

        for(int j = 0; j < maxSize; j++)

        {

            long n = (long)( java.lang.Math.random()*(maxSize-1) );

            a[j] = n;

        }

       

        // sort using quick sort

        merge_sort(a, 0, a.length - 1);

       

        display(a);

    }

}

Sample Output