In previous articles, we analyzed bubble sort, insertion sort, and selection sort. But their actual complexity is order n squared. Let’s do merge sort this time with less time.

thought

Merge sort uses the idea of divide-and-conquer, which has three steps at each level of recursion:

  1. Divide: Divide n elements into n/2 element subsequences.
  2. Conquer: Sort two subsequences recursively with merge sort.
  3. Combine: Combine two sorted subsequences to obtain sorted results.

Thought diagram

Specifically, we take a group of unordered sequence {14,12,15,13,11,16} as an example for decomposition, as shown in the figure below:

code

The recursive implementation

/ / the recursive implementation merge sort public static void mergeSort_recursion (int [] arr) {if (arr = = null | | arr. Length < 2) {return; } process(arr,0,arr.length-1); } //L ... Private static void process(int[] arr, int L, int R){if (L ==R){return; Int mid = L +((R-L) >>1); Process (arr,L,mid); process(arr,mid+1,R); merge(arr,L,mid,R); Private static void merge(int[] arr, int L, int M, int L) private static void merge(int[] arr, int L, int M, int L) Int [] help = new int[r-l +1]; int i = 0; int p1 = L; int p2 = M+1; While (p1 & p2 < = M < = R) {/ / prevent an array / / i++ ascribed to + + help [i++] = arr (p1) < = arr (p2)? arr[p1++]:arr[p2++]; } / / the aftermath, p1 cross a line, or the p2 cross-border while (p1 < = M) {help [i++] = arr (p1 + +); } while (p2<=R){ help[i++] =arr[p2++]; } for (i=0; i<help.length; i++){ arr[L+i] = help[i]; }}Copy the code

Non-recursive implementation

/ / the recursive method to realize the public static void mergeSort (int [] arr) {if (arr = = null | | arr. Length < 2) {return; } int N = arr.length; Int mergeSize = 1; While (mergeSize<N){// mergeSize<N; While (L<N){if (mergeSize>= n-l){mergeSize>= n-l; } int M = L+mergeSize-1; int R = M+Math.min(mergeSize,N-M-1); Merge (arr,L,M,R); } if (mergeSize> N/2){break; } mergeSize<<=1; // Adjust the step size to 2 times the original}}Copy the code

Variant of the merge sort idea

For minimum and

In an array, the sum of the smaller numbers to the left of a number is called the small sum, and the sum of all the smaller sums is called the small sum of the array. Find the small sum of the array. For example [1, 3, 4, 2, 5]

  • Numbers less than 1 to the left of 1: None
  • The number to the left of 3 less than 3:1
  • Numbers to the left of 4 less than 4:1, 3
  • The number to the left of 2 less than 2 is: 1
  • The number less than 5 to the left of 5 is: 1, 3, 4, 2
  • So the small sum of this array is: 1+1+3+1+1+3+4+2 = 16

Code and Ideas

public static int smallSum(int[] arr) { if (arr == null || arr.length < 2) { return 0; } return process(arr, 0, arr.length - 1); } // arr[L..R] {return small sum; Public static int process(int[] arr, int l, int r) {if (l == r) {return 0; } // l < r int mid = l + ((r - l) >> 1); return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r); } // public static int merge(int[] arr, int L, int m, int r) { int[] help = new int[r - L + 1]; int i = 0; int p1 = L; int p2 = m + 1; int res = 0; While (p1 <= m && p2 <= r) {// if (p1 <= m && p2 <= r) {// if (p1 <= m && p2 <= r) {// if (p1 <= m && p2 <= r) {// if (p1 <= m && p2 <= r) {// if (p1 <= m && p2 <= r) { // why (r-p2 + 1) * arr[p1]? Since both sides are sorted, if the number in p2 is larger than the number in P1, then there will be (r - p2 + 1) larger than the number in P1, because P1 will move to the right, So will be only one / / 1 2 3 4 | 0 3 6 / / p1, p2 / p1 / p2 = = = = = = > R - p2 + 1 number is greater than p1 location number/p1 / p2 = = = = = = > R - p2 + 1 number is greater than p1 location number res + = arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0; 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 (i = 0; i < help.length; i++) { arr[L + i] = help[i]; } return res; }Copy the code