Merge sort algorithm idea:
Divide - conquer; each recursive process involves three steps. First, decomposition: decompose the sequence of n elements to be sorted into two subsequences, each subsequence including n/2 elements.
Second, Governance: Call MergeSort on each subsequence separately and perform recursive operations. Third, Merge: Merge two sorted subsequences to generate sorting results.
public static void mergeSort(int[] a, int[] tmp, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(a, tmp, left, mid);// Left sorting mergeSort(a, tmp, mid + 1, right);// Right sorting merge(a, tmp, left, mid + 1, right);// Merge left and right} }public static void merge(int[] a, int[] tmp, int left, int rightPos, int right) { int leftEnd = rightPos - 1; int tmpPos = left; int num = right - left + 1; while (left <= leftEnd && rightPos <= right) { if (a[left] < a[rightPos]) { tmp[tmpPos++] = a[left++]; } else { tmp[tmpPos++] = a[rightPos++]; } } while (left <= leftEnd) { tmp[tmpPos++] = a[left++]; } while (rightPos <= right) { tmp[tmpPos++ ] = a[rightPos++]; } for (int i = 0; i < num; i++, right--) { a[right] = tmp[right]; } }Schematic diagram of the merge algorithm:
The above is the entire content of this article, I hope you all like it.