This is the 11th day of my participation in Gwen Challenge

1. What is divide and rule

Divide and rule is a strategy. It’s an idea

Divide A big problem into the same two or more small problems that are unrelated to each other, solve each problem separately, and combine the solutions to the small problems so that the big problem is solved. Once the small problems are related, for example A big problem A is divided into A1, A2, A3, A4, If none of these four problems are related, they can all be solved independently, which is the idea of divide-and-conquer. If the results of A2 are related to A1, and the results of A4 are related to A3, this is not divide-and-conquer. This is called dynamic programming

How divide-and-conquer is used, divide-and-conquer is actually used very much, for example, in the top ten classical algorithms of computer, there are three using the idea of divide-and-conquer, they are merge sort, quick sort, and binary search, as well as big data technology MapReduce is the application of the idea of divide-and-conquer. So divide and conquer is very, very important in the computer world

2. Merge sort

For an array, the data sequence is divided into smaller and smaller half-sublists by recursive and dial-and-conquer techniques. After sorting the half-sublists, the sorted half-sublists are combined into larger and larger ordered sequences by recursive methods

If two ordered tables are combined into one ordered table, it is called 2-way union, and the corresponding multi-way union

In order to improve the performance, we sometimes use other sorting algorithms for half-subtables when the number of half-subtables is less than a certain number

And the sorting diagram

Split the original array into subtables

Then sort the subtables

Once the small problem is solved (after the small table is sorted), we start to merge the values in subtable 1 and compare and sort the values in subtable 2

The above is the idea of parallel sorting, that is, the use of the idea of divide-and-conquer, a large unnecessary array is split into many small arrays, sorting merge, get an ordered large array

3. Code implementation

 public static int[] sort(int[] array) {
        if(array.length<=49) {return InsertionSort.sort(array);// Insert sort
        }else{
            /* Splits the array and recursively calls */
            int mid = array.length / 2;
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            returnmerge(sort(left), sort(right)); }}/** * merge sort -- combine two sorted arrays into a sorted array **@param left
     * @param right
     * @return* /
    public static int[] merge(int[] left, int[] right) {//
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)/* The value of the left array is complete, and the value of the right array is complete
                result[index] = right[j++];
            else if (j >= right.length)/* Select * from left array */
                result[index] = left[i++];
            else if (left[i] > right[j])/* The value of the element in the left array is greater than the value of the element in the right array
                result[index] = right[j++];
            else/* The value of the element in the right array is greater than the value of the element in the left array
                result[index] = left[i++];
        }

        return result;
    }
Copy the code

That’s the code for sorting

3, summarize

The idea of divide and conquer has been used in many applications, such as mapReduce for big data, ForkJoin for threading, etc. This is also the foundation for learning ForkJoin.