Merge Sort

/* Java program for Merge Sort */

class MergeSort
{
    void sort(int[]arr,int start,int end)
    {
        if(start<end)
        {
            int middle=(start+end)/2;
            sort(arr,start,middle);
            sort(arr,middle+1,end);
            merge(arr,start,middle,end);
        }
    }
    void merge(int[] arr,int start,int middle,int end)
    {
        int[] temp=new int[arr.length];     // Create copy of Array
        for(int i=start;i<=end;i++)
        temp[i]=arr[i];
       
        int i=start,j=middle+1;         //initialize left and right Index
        int k=start;                           // initialize merged index
        while(i<=middle && j<=end)
        {
            if(temp[i]<=temp[j])
            {
                arr[k]=temp[i];
                i++;
            }
            else{
                arr[k]=temp[j];
                j++;
            }
            k++;
        }
        while(i<=middle)  // Copy remaining elements
        {
            arr[k]=temp[i];
            i++;
            k++;
        }
        while(j<=end)     // Copy remaining elements
        {
            arr[k]=temp[j];
            j++;
            k++;
        }
    }

// Driver method
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 7};

System.out.println("Given Array");
printArray(arr);

MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);

System.out.println("\nSorted array");
printArray(arr);
}
  /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}