Merge sort

thought

An array is divided into groups at one level. The groups are sorted internally, and then several groups are merged and sorted
Use the picture made by Mr. Han Shunping of Shang Silicon Valley
In short, thought is divide and rule
###Code implementation
Let's put the main function up first

public static void main(String[] args) {
        int[] arr ={6,1,3};
        int []temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

This mergeSort is the way to merge and sort

Number of groups

public static void mergeSort(int[] arr, int left, int right, int[] temp){
 System.out.println("left yes"+left+"  right yes"+right);
 //You can see left and right in recursion through this
    if(left <right){
    int mind=(left+right)/2;
    mergeSort(arr,left,mind,temp);
    mergeSort(arr,mind+1,right,temp);
    }

The above if (left < right) is very critical
When there is only one number in the recursion group, you need to exit the recursion
Because what order do you shoot a number? Compare the size of the number to at least two numbers
If there is only one number, it will be left=right
The picture given by the teacher is that the array has even numbers. What if there is an extra number in the odd number group?

The answer is that odd numbers do not participate in the last grouping

Suppose there are three numbers 123
First grouping 123
Second grouping 12 and 3
To the third grouping 1 and 3 (because it does not meet left < right, it does not enter the if to complete recursion)

Put the separate groups together

This part is the hardest

This step is
Sort → close → reorder → close again
Until completion

After the division, there will be the left part and the right part
There are two pointers on both sides
Select the smallest of the two pointers and put it into another array
Move the pointer backward after placing the number
If one side has been placed, there is no brain to put the other half into another array one by one
After all the numbers are placed, put the ordered numbers in another array back to the original array

Here's another picture of Mr. Han Shunping

First, put the numbers on the left and right sides into another array in order

    public static void merge(int[] arr, int left, int mind,int right, int[] temp){
    int l=left;
    int m=mind+1;
    int t=0;
    while(l<=mind&&m<=right){
        if(arr[l]<=arr[m]){
            temp[t]=arr[l];
            t++;
            l++;
        }
       else  {
            temp[t]=arr[m];
            t++;
            m++;
        }
    }
    //Note that the above is to put it all over again
//==============================================
//Note that the following is when you finish playing it again
//Put the other side directly into the brain
while(l<=mind){
    temp[t]=arr[l];
    l++;
    t++;
}
while(m<=right){
    temp[t]=arr[m];
    m++;
    t++;
}
    }

Let's think about why when one side is finished, the other side can be mindless

The answer is because the following while must be executed in order
Because recursion must be executed to the end and then returned upward
The one above recurses to two numbers
A number on the left and a number on the right
They compare each other and put them in another array
)Take it back again and there will be order

Here is the merged code

		int lf=left;
		int t1=0;
        System.out.println("left yes"+lf+"  right yes"+right);
    while(lf<=right){
       arr[lf] =temp[t1];
       lf++;
       t1++;
    }

This is to get the sorted numbers back from another array temp

Here's why t1 of temp is defined as 0

Because this space is only used for sorting
So it's okay if the numbers in its space are overwritten
Let's say that the sort array has four numbers 1 2 3 4
The four spaces of temp are as follows:
1 2
3 4
1 2 3 4

The following is the sort merge overall code

 public static void merge(int[] arr, int left, int mind,int right, int[] temp){
    int l=left;
    int m=mind+1;
    int t=0;
    while(l<=mind&&m<=right){
        if(arr[l]<=arr[m]){
            temp[t]=arr[l];
            t++;
            l++;
        }
       else  {
            temp[t]=arr[m];
            t++;
            m++;
        }
    }
		while(l<=mind){
    	temp[t]=arr[l];
    	l++;
    	t++;
	}
		while(m<=right){
    	temp[t]=arr[m];
    	m++;
    	t++;
	}


		int lf=left;
		int t1=0;
        System.out.println("left yes"+lf+"  right yes"+right);
    while(lf<=right){
       arr[lf] =temp[t1];
       lf++;
       t1++;
    }
    
    }

Overall code

import java.util.Arrays;

public class MergetSort {
    public static void main(String[] args) {
        int[] arr ={1,3,6};
        int []temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }
    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        System.out.println("left yes"+left+"  right yes"+right);
    if(left <right){
    int mind=(left+right)/2;
    mergeSort(arr,left,mind,temp);
    mergeSort(arr,mind+1,right,temp);
    merge(arr,left,mind,right, temp);

    }
    }


    public static void merge(int[] arr, int left, int mind,int right, int[] temp){
    int l=left;
    int m=mind+1;
    int t=0;
    while(l<=mind&&m<=right){
        if(arr[l]<=arr[m]){
            temp[t]=arr[l];
            t++;
            l++;
        }
       else  {
            temp[t]=arr[m];
            t++;
            m++;
        }
    }
		while(l<=mind){
		    temp[t]=arr[l];
		    l++;
		    t++;
		}
		while(m<=right){
   		 temp[t]=arr[m];
   		 m++;
	    t++;
		}


		int lf=left;
		int t1=0;
        System.out.println("left yes"+lf+"  right yes"+right);
   	 while(lf<=right){
       arr[lf] =temp[t1];
       lf++;
       t1++;
    	}
    	}
}