Merge sort

The whole idea

Partition (divide and conquer)

Specific steps

  1. Sort Splits an array into sorted elements. {1} or {47} defaults to sorted if there is only one element
  2. Merge Stores sorted arrays in a temp array by size. The left and right arrays are scanned and the digits are placed in the temp array from smallest to largest. However, the scanning process may end with the left array or end with the right array.

For example, {38,49} {65,97} during the merge, 38 and 49 enter the temp array one by one. However, the numbers in the right array are not manipulated. Therefore, you need to determine the value.

Code Sort

Public static int[] sort(int[] a,int low,int high){public static int[] sort(int[] a,int low,int high){ If (low<high){// Sort (a,low,mid); Sort (a,mid+1,high); / / merge the merge (a, low, mid, high); } return a; }Copy the code

Specific code Merge

Public static void merge(int[] a, int low, int mid, int high) {int[] temp = new int[high-low+1]; int i = low; int j = mid+1; int k = 0; while(i<=mid && j<=high){ if (a[i]<a[j]){ temp[k++] = a[i++]; }else{ temp[k++] = a[j++]; } } while (i<=mid){ temp[k++] = a[i++]; } while(j<=high){ temp[k++] = a[j++]; For (int x= 0; for (int x= 0; x<k; x++){ a[low+x] = temp[x]; }}Copy the code

Case study:

44,2,77,34,12,87,14,1 int [] a = {};

Sorting result

[1, 2, 12, 14, 34, 44, 77, 87]

Improvable part

Sort sort declares temp temp variables in advance to prevent repeated object creation in recursive calls.