> ### 归并排序 * 时间复杂度`O(nlogn)`，最坏情况`O(nlogn)`，**稳定** ``` //归并排序 public void sort5(int[] arr, int left, int right) { int mid = (left + right) / 2; if(left < right) { this.sort5(arr, left, mid); this.sort5(arr, mid + 1, right); merge(arr, left, mid, right); } } public void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int t1 = left, t2 = mid + 1, t = 0; while(t1 <= mid && t2 <= right) { temp[t++] = arr[t1] < arr[t2] ? arr[t1++] : arr[t2++]; } while(t1 <= mid) { temp[t++] = arr[t1++]; } while(t2 <= right) { temp[t++] = arr[t2++]; } t = 0; while(t < temp.length) { arr[left + t] = temp[t]; t++; } } ```