Merge sort

Realization principle

Put two unordered “ Small ” All elements of the array are orderly filled into a new array , Finish sorting at the same time “ Merge ”.

First compare the first element in the two arrays , Fill the new array with smaller numbers （ Ascending ）

Compare the next element of the array that has taken the data with the previous one that has not taken the data , Then fill the new array with smaller numbers

3

5

Repeat the same operation , Until the last one is put in

3

5

6

7

Divide and conquer strategy （ Divide and rule ）

The actual array will be split repeatedly , Get a small array （ The length is 1）, Then sort and merge

Divide and conquer

Divide the problem into small ones , And then solve it recursively , Then combine the problems obtained in different stages

recursive

Inside the method , Call the current method itself

For example, in a() Method a() Method

Only when calling internally a() Method a() Method , Will continue to run the external a() Method the rest of the code

Unskilled , Be careful with recursion , Otherwise, it will form “ Dead cycle ” effect

Realization thought

Split the array in two

In the middle ： The first subscript of the upper array +（ The maximum subscript of the upper array - The first subscript of the upper array ）/2

left ： The first subscript of the upper array - In the middle

On the right side ： In the middle +1- The maximum subscript of the upper array

 

Implementation code

import java.util.Arrays;
import java.util.Random;

public class MergeSort {
    /**
     *
     * @param array  The original array 
     * @param left   Left position 
     * @param right  Right position 
     * @return   New array after arrangement 
     */
    public static int[] mergeSort(int[] array ,int left ,int right){
        // If the starting and ending subscripts are consistent, it means that the current array has only one element , We can't divide any more 
        if (left == right){
            return new int[]{array[left]};// Return this array 
        }
        // Determine the middle position 
        int middle = left + (right - left)/2;
        // Left array value range   From the left position of the upper array to the middle point 
        int[] leftArray = mergeSort(array ,left ,middle);
        // Right array value range   The middle point of the upper array is one bit to the right to the right 
        int[] rightArray = mergeSort(array ,middle + 1 ,right);
        // The length of the reordered array is the length of the addition of the two arrays 
        int[] newArray = new int[leftArray.length + rightArray.length];
        // Left array start subscript 
        int l = 0;
        // Right array start subscript 
        int r = 0;
        // New array start subscript 
        int m = 0;
        // When the left array loop is completed or the right array is traversed, the loop ends 
        while (leftArray.length > l && rightArray.length > r){
            // Compare the size of the two arrays and put the smaller elements into the new array , At the end of the operation , The subscript of the array with data movement and the new array +1
            newArray[m++] = leftArray[l] > rightArray[r]?rightArray[r++]:leftArray[l++];
        }
        // After the loop ends, there will be the remaining array, in which all the elements will be put into the new array 
        while (l < leftArray.length){
            newArray[m++] = leftArray[l++];
        }
        while (r < rightArray.length){
            newArray[m++] = rightArray[r++];
        }
        return newArray;
    }
    public static void main(String[] args) {
        Random rd = new Random();
        // Generating arrays 
        int[] arr = new int[rd.nextInt(100)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rd.nextInt(500);
        }
        System.out.println(Arrays.toString(arr));
        // Calling method 
        int[] brr = mergeSort(arr ,0 ,arr.length-1);
        System.out.println(Arrays.toString(brr));
    }
}