MERGE SORT USING RECURSION

/* Java program for Merge Sort */
class msrk
{
    static void sort(int a[], int p, int r)
    {
        if (p < r)
        {
            // Find the middle point
            int q = (p+r)/2;

            // Sort first and second halves
            sort(a, p, q);
System.out.printf("\n\t left sort pivot element a[%d]=%d ", p,a[p]);
            sort(a , q+1, r);
System.out.printf("\n\n right sort pivot element a[%d]=%d ", q+1,a[q+1]);
            // Merge the sorted halves
            merge(a, p, q, r);
System.out.printf("\n\n right sort pivot element a[%d]=%d ", q+1,a[q+1]);
        }
    }
    public static void main(String args[])
    {
        int a[] = {2, 8, 6, 1, 4, 3};
        int n = a.length;
        for (int i=0; i<n; i++)
            System.out.print(a[i]+" ");
               
        sort(a, 0, n-1);

        System.out.printf("\n sorted array :");
        for (int i=0; i<n; i++)
            System.out.print(a[i]+" ");
        }
   
    static void merge(int a[], int p, int q, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = q - p + 1;
        int n2 = r - q; // r-(q+1)+1  r-q-1+1

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            {L[i] = a[p + i];
System.out.printf("\n\t left array element a[%d]=%d ", i,L[i]);}
        for (int j=0; j<n2; ++j)
            {R[j] = a[q + 1+ j];
System.out.printf("\n\n right array element a[%d]=%d ", j,R[j]);}

        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged sub array
        int k = p;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                a[k] = L[i];
                i++;
            }
            else
            {
                a[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            a[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            a[k] = R[j];
            j++;
            k++;
        }
    }
}


OUTPUT