Recursion and merge sort

recursive ：

（1）master The formula ：, The time complexity of Solving Recursive behaviors with the same size of subproblems , Its time complexity is based on a,b,d The relationship between them is determined as follows ：

;

;

;

among ：N It is the scale of the parent problem ,a Is the number of calls to the recursion problem ,b It is the mother problem that is decomposed into how many And so on The sub problem of , The second addend is the time complexity of the remainder except the subproblem

Merge sort ：

Sort outside the whole , That is, use extra space , After arranging the order , Then copy the data in the extra space back to the original array

  The space complexity of merging is the space occupied by the temporary array and the data pushed into the stack during recursion ：n + logn; So the space complexity is zero : O(n)

principle ： Divide the original array into left and right halves , Make the left half orderly and the right half orderly , Then combine the two halves into an ordered array . Using recursion , The left half can be divided again , The right half is the same , Until there is only one element left in each half , Then go back up , Layer by layer merge .

advantage ： Compared with simple sorting , Merge sort does not waste the previous comparison results in determining the position of each element , Each comparison is not independent , Instead, it is transformed into a part of the overall order in each comparison , Therefore, the time complexity is low .

 // Merge sort 

    /**
     *  Overall merge and sort framework , Using recursion , Time complexity  O(N*logN)
     *  You can specify the range to sort [l,r]
     *  External sorting , Use the extra space and copy it back 
     *  The essence ： The merged parts of each comparison are not wasted , Become a part of the whole, pass it on and use it 
     * @param arr： Array to sort 
     * @param l： The subscript to the left of the merge sort 
     * @param r： The subscript to the right of the merge sort 
     */
    public static void mergeSort(int[] arr, int l, int r){
        if(l == r) return;
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);// Merge and sort the left half 
        mergeSort(arr, mid + 1, r);// Merge and sort the right half 
        merge(arr, l, mid, r);// Merge the left and right sides of the order 
    }

    // Merger 

    /**
     *  Merge the ordered arrays of the left and right halves 
     * @param arr： An ordered array of left and right halves 
     * @param l：arr Left subscript of 
     * @param m：arr The middle subscript of 
     * @param r：arr Right subscript of 
     */
    public static void merge(int[] arr, int l, int m, int r){
        int[] help = new int[r - l + 1];// Auxiliary array , The size is equal to the size of the range to be arranged 
        int i = 0;
        int p1 = l, p2 = m + 1;
        while(p1 <= m && p2 <= r){
            help[i++] = arr[p1] >= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= m){
            help[i++] = arr[p1++];
        }
        while (p2 <= r){
            help[i++] = arr[p2++];
        }
        for(int j = 0; j < help.length; j++){
            arr[l + j] = help[j];//！！！！
        }
    }

application ： Small and problem

Find the number whose left side of each number in the given range is smaller than your own and sum it , And then add these together .

Method ： Merge and find the number of numbers on the right side of each number that are larger than your own m, And then there is m Add the numbers . Start from the lowest level with only one element and merge in turn , Count how many numbers are larger on the right than on the left , Merge and sort again , Sum again

Be careful ： Different from the traditional merge sort , When the numbers on the left and right sides are equal , First, put the number on the right in the extra array in order . Because if you put the number on the left first , The small sum produced by this number is skipped .

In the process of summation , Neither omission , And don't repeat it . The reason for not omitting is that in the process of merging, it successively merges from one expansion to the whole , No repetition because after the summation is completed and merged into a whole , No more small sums in a whole .

  // Small and problem 
    public static int smallSum(int[] arr, int l, int r){
        if(arr == null || arr.length < 2 || l == r) return 0;
        int m = l + ((r - l) >> 1);
        // The small sum of the left half + The small sum of the right half + The small sum obtained by merging the left and right sides 
        return smallSum(arr, l, m) + smallSum(arr, m + 1, r) + smallSumMerge(arr, l, m, r);
    }

    public static int smallSumMerge(int[] arr, int l, int m, int r){
        int res = 0;
        int[] help = new int[r - l + 1];
        int i = 0, p1 = l, p2 = m + 1;
        while(p1 <= m && p2 <= r){
            res += arr[p2] > arr[p1] ? (r - p2 + 1) * arr[p1] : 0;//！！！！！ Because this half is already in order , therefore r To p2 The number of ranges is larger than the current arr[p1] Big , Each one should be added once arr[p1]
            help[i++] = arr[p2] > arr[p1] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m){
            help[i++] = arr[p1++];
        }
        while (p2 <= r){ // There is no need to add the large number in the second half even if it is left , Because the first loop uses (r - p2 + 1), It's been added 
            help[i++] = arr[p2++];
        }
        for(int j = 0; j < help.length; j++){
            arr[l + j] = help[j];
        }
        return res;
    }

Reverse order pair problem ： The number on the left is larger than the number on the right to form an inverse pair （ Contrary to small sum ）