How to Implement Merge Sort in Java

In this example, we can get the method of merge sort in Java.

Source Code

package com.beginner.examples;

import java.util.Arrays;

public class MergeSortExample {

    public static void main(String[] args) {

        int[] arr = {10,34,235,22,1,93};

        sort(arr,0,arr.length-1);

        System.out.println(Arrays.toString(arr));

    }

    private static void sort(int[] arr,int left,int right)
    {
        if(left < right)
        {
            int mid = (left + right)/2;// middle value
            sort(arr,left,mid);//  sort the left of arr
            sort(arr,mid+1,right);//  sort the right of arr
            merge(arr,left,mid,right); // merge
        }
    }
    private static void merge(int[] arr, int left, int mid, int right) 
    {        
        int i = left;
        int j = mid + 1;
        int k = 0;
        int l = 0;
        int[] num = new int[right - left + 1];
        //move smaller numbers to new array
        while(i <= mid&&j <= right)
        {
            if (arr[i] < arr[j]) {
                num[k++] = arr[i++];
            } else {
                num[k++] = arr[j++];
            }
        }
        // Move the remaining left numbers into the array
        while(i <= mid)
        {
            num[k++] = arr[i++];
        }
        // Move the remaining right numbers into the array
        while(j <= right)
        {
            num[k++] = arr[j++];
        }
        for (l = 0; l < num.length; l++) 
        {
            arr[l + left] = num[l];
        }
    }
}

Output:

[1, 10, 22, 34, 93, 235]

References

Imported packages in Java documentation:

Arrays