## 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++; } } }