Recursive way

Recursive method to achieve the maximum value of the array

    @Test
    public void TestMax() {
    
        int a[] = {
    0, 1, 2, 5, 3, 2, 1, 8, 4, 2, 0};
        System.out.println(getMax(a));
    }

    public int getMax(int[] arr) {
    
        return recursion(arr, 0, arr.length - 1);
    }

    //arr[l...r] Find the maximum value on the range 
    public int recursion(int[] arr, int l, int r) {
    
        if (l == r) {
         //arr[l...r] There is only one number in the range , Go straight back to 
            return arr[l];
        }
        int mid = l + ((r - l) >> 1); // Finding the midpoint , Prevent overflow 
        int leftMax = recursion(arr, l, mid);
        int rightMax = recursion(arr, mid + 1, r);
        return Math.max(leftMax, rightMax);
    }

Merge sort

• The core idea used Divide and conquer

Local sort first ,,,,,, Then sort the whole

First, divide a complete array into two halves （ Left half , Right half , Then divide the left side into two halves ,,,,, Until it can't be further divided , Then sort ,,,, Left row , The right row ...） Finally, the overall order

Space for time
Time complexity O(nlogn)

 @Test
    public void sort(){
    
        int a[]={
    2,5,4,6,9,7,1,0};
        process(a,5,7);
        for (int i = 0; i < 8; i++) {
    
            System.out.print(a[i]);
        }
    }

    /** *  recursive , Bisection order  * @param arr * @param l * @param r */
    public void process(int[] arr, int l, int r) {
    
        if (l == r) {
    
            return;
        }
        int mid = l + ((r - l) >> 1);
        process(arr, l, mid);   // Order on the left 
        process(arr, mid + 1, r);   // Order on the right 
        merge(arr, l, mid, r);
    }

    /*** *  Sort  * @param arr * @param l * @param mid * @param r */
    private void merge(int[] arr, int l, int mid, int r) {
    
        int[] help = new int[r - l + 1];   // Store the locally ordered array 
        int i = 0;  // Index for new array 
        int j = l;
        int k = mid + 1;
        while (j <= mid && k <= r) {
    
            help[i++] = arr[j] <= arr[k] ? arr[j++] : arr[k++];
        }
        while (j<=mid){
    
            help[i++] = arr[j++];
        }
        while (k<=r){
    
            help[i++] = arr[k++];
        }

        /** *  Assign the ordered new array to the old array  */
        for (i = 0; i < help.length; i++) {
    
            arr[l+i] = help[i];
        }
    }

Extension of merge sort