5.4. Merge and sort

5.4.1. I. the concept and its introduction ¶

Merge sorting (Merge sort) is an effective and stable sorting algorithm based on merge operation, which is a very typical application of divide-and-conquer (Divide and Conquer). The ordered subsequences are merged to get a completely ordered sequence, that is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called two-way merging.

5.4.2. II. Applicable instructions ¶

When there are n records, logn round merge sorting is needed. In each round of merge, the number of comparisons is no more than n, and the number of element movements is n. Therefore, the time complexity of merge sorting is O (nlogn). Merging and sorting requires storage space equal to the number of records to be sorted, so the space complexity is O (n).

Merge sorting is suitable for scenarios where the amount of data is large and stability is required.

5.4.3. III. Process diagram ¶

Merge sorting is an example of a recursive algorithm, in which the basic operation is to merge two sorted arrays, take two input arrays An and B, one output array C, and three counters I, j, k, their initial positions are placed at the beginning of the corresponding array.

A [i] And B. [j] Copy the smaller one to the next location in C, and the relevant counter moves forward.

When one of the two input arrays is used up, the rest of the other array is copied to C.

Top-down merge sorting, recursive grouping diagram:

Merge and sort two sets of data in the third row

Merge and sort the data in a group of four in the second row

Merge and sort as a whole

5.4.4. 4. Java instance code ¶

源码包下载： Download

public class MergeSort { // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 private static void merge(Comparable[] arr, int l, int mid, int r) { Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1); // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1 int i = l, j = mid + 1; for (int k = l; k <= r; k++) { if (i > mid) { // 如果左半部分元素已经全部处理完毕 arr[k] = aux[j - l]; j++; } else if (j > r) { // 如果右半部分元素已经全部处理完毕 arr[k] = aux[i - l]; i++; } else if (aux[i - l].compareTo(aux[j - l]) < 0) { // 左半部分所指元素 < 右半部分所指元素 arr[k] = aux[i - l]; i++; } else { // 左半部分所指元素 >= 右半部分所指元素 arr[k] = aux[j - l]; j++; } } } // 递归使用归并排序,对arr[l...r]的范围进行排序 private static void sort(Comparable[] arr, int l, int r) { if (l >= r) { return; } int mid = (l + r) / 2; sort(arr, l, mid); sort(arr, mid + 1, r); // 对于arr[mid] <= arr[mid+1]的情况,不进行merge // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失 if (arr[mid].compareTo(arr[mid + 1]) > 0) merge(arr, l, mid, r); } public static void sort(Comparable[] arr) { int n = arr.length; sort(arr, 0, n - 1); } // 测试MergeSort public static void main(String[] args) { int N = 1000; Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000); sort(arr); //打印数组 SortTestHelper.printArray(arr); } }