What is the merge sort and Master Formula in java

What is the merge sort and Master formula in java? aiming at this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

Basic thought

Merge and sort with the idea of divide and conquer. Borrow a picture to illustrate it.

The n elements are cut from the middle and divided into two parts. (there may be one more number on the left than on the right.) divide step 1 into two parts, and then decompose them recursively. Until the number of elements in all parts is 1. Gradually merge two sequenced sequences from the bottom.

The advantage is that after divide and conquer, the time complexity of the merge sorting process is O (N) (only one scan is needed to combine two ordered numbers into an ordered array)

Implement public static void MergeSort (int [] arr,int l, int r) {if (l = = r | | r < 0) {return;} int middle = 1 + (rmerl) / 2; / / take the middle value to prevent Integer.MaxValue overflow MergeSort (arr,l,middle); MergeSort (arr,middle+1,r); sort (arr,l,middle,r) } / * * @ param arr Array waiting to be sorted * @ first pointer to param l left Array * @ param middle split left Array * @ param r Last pointer to the right Array * / private static void sort (int [] arr, int l, int middle, int r) {int [] temp = new int [arr.length] System.arraycopy (arr, 0, temp, 0, arr.length); int right_first = middle+1; int tempIndex = l; while (l