Creating recursive mergesort method

Question

I am currently trying to implement the merge sort method to sort an array filled with random numbers. The main method tells whether the array is properly sorted or not.

So far, I have written the method to the best of my ability but no matter what I try I cannot understand why my merge sort is not working. I dont understand merge sort very well, so any help is appreciated

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args)
    {
        int[] start = new int[100];
        for(int i = 0; i < start.length; i++)
        {
            start[i] = (int)(Math.random()*20 + 1);
        }
        int[] sorted = Arrays.copyOf(start,start.length);
        Arrays.sort(sorted);
        mergesort(start);
        if(Arrays.equals(start, sorted))
            System.out.print("correctly sorted");
        else
            System.out.print("not properly sorted");
    }
    
    
    public static void mergesort(int[] arr)
    {
        //base case then general case
        //all merging code, no sorting

        //base case
        if(arr.length ==0 || arr.length < 2 || arr.length <=1)
        {
            return;
        }
        //divide
            int half = arr.length/2;
            int[]arr1 = new int[half];
            for(int i =0; i<half; i++)
            {
                arr1[i] = arr[i];
            }
            int[]arr2 = new int[arr.length - half];
            for(int i =half; i<arr.length; i++)
            {
                arr2[i-half]= arr[i];
            }

            //merging
            int[]merge = new int[arr1.length+arr2.length];

            int k = 0;
            int i=0;
            int j=0;
            while(i<arr1.length && j<arr2.length)
                {
                    if(i<arr1.length && (j>=arr2.length || arr1[i]<=arr2[j]))
                    {
                        merge[k++] = arr1[i++];
                    }
                    else
                    {
                        merge[k++] = arr2[j++];
                    }
                }
            
                while(i<arr1.length)
                {
                    merge[k++] = arr1[i++];
                }

                while(j<arr2.length)
                {
                    merge[k++] = arr2[j++];
                }


        
        
    }

}

Everytime I run the code, I always get "not properly sorted"

Answer 1

After splitting arr into arr1 and arr2, mergesort needs to call itself to sort arr1 and arr2, then merge arr1 and arr2 back into arr. Fixes noted in comments. Also cleaned up some of the code and spacing.

public static void mergesort(int[] arr)
{
    //base case then general case
    //all merging code, no sorting

    //base case
    if(arr.length < 2)
    {
        return;
    }
    //divide
    int half = arr.length/2;
    int[]arr1 = new int[half];
    for(int i=0; i<half; i++)
    {
        arr1[i] = arr[i];
    }
    int[]arr2 = new int[arr.length - half];
    for(int i=half; i<arr.length; i++)
    {
        arr2[i-half]= arr[i];
    }

    mergesort(arr1);                // fix
    mergesort(arr2);                // fix

    // arr = merge(arr1, arr2)      // fix

    int k = 0;
    int i=0;
    int j=0;
    while(i<arr1.length && j<arr2.length)
    {
        if(arr1[i]<=arr2[j])
        {
            arr[k++] = arr1[i++];
        }
        else
        {
            arr[k++] = arr2[j++];
        }
    }

    while(i<arr1.length)
    {
        arr[k++] = arr1[i++];
    }

    while(j<arr2.length)
    {
        arr[k++] = arr2[j++];
    }
}