1. The train of thought Before and after the array from the middle into two arrays, and then continue to before and after the two arrays in the middle is divided into smaller, until in each array only one element, the equivalent of each array is orderly array, the two merged into one size of 1 array size is 2, in the size of an array of 2 merge into 4… Until all the small arrays merge. So the code for merge sort is really just a method for splitting an array plus a method for merging two ordered arrays.

2. The illustration

3. Code implementation

Public int[] mergeSort(int[] arr, int left, int right) { If (left < right) {int mid = (left + right) / 2; Arr = mergeSort(arr, left, mid); Arr = mergeSort(arr, mid + 1, right); // Merge (arR, left, mid, right); } return arr; } // Merge two ordered arrays, [left,mid] into one array, Public void merge(int[] arr, int left, int mid, Int right) {// Define temporary array int[] temp = new int[right-left + 1]; int i = left; int j = mid + 1; // Temporary array subscript int k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; For (int value: temp) {arr[left++] = value; }}Copy the code

4. Properties ① Time complexity :O(Nlogn) ② space complexity :O(n) ③ Non-in-situ sorting ④ stable sorting