Overview
Merge sorting method is to merge two (or more than two) ordered tables into a new ordered table, that is, divide the sequence to be sorted into several subsequences, each subsequence is ordered. Then the ordered subsequences are merged into the overall ordered sequence.
Merge sorting is implemented using recursion, which belongs to "dividing and conquer". The target array is divided into two from the middle, and then the two arrays are sorted separately. After the sorting is completed, the two arrays are "merged" together. The most important thing in merge sorting is the "merge" process. In the merge process, additional space that is consistent with the two arrays that need to be merged is required.
Reproduction image:
step
Apply space so that its size is the sum of two sorted sequences. This space is used to store the merged sequence to set two pointers. The initial position is the starting position of the two sorted sequences, compare the elements pointed to by the two pointers, select relatively small elements and put them into the merged space, and move the pointer to the next position. Repeat step 3 until a pointer reaches the end of the sequence. Copy all the remaining elements of the other sequence directly to the end of the merged sequence.
Raw data:
3 5 2 6 2
The prerequisite for merging is to separate the arrays, divide them into two, and then divide them into two, and they cannot be divided again, and merge them.
The first round is separated, index 2 ((0+4)/2=2) is the middle
[3 5 2] [6 2]
The second round of separation, separate [3 5 2]
[3 5] [2] [6 2]
The third round of separation, separate [3 5]
[3] [5] [2] [6 2]
Merge[3][5]
[3 5] [2] [6 2]
Merge[3 5][2]
[2 3 5] [6 2]
The fourth round is separated, separates [6 2]
[2 3 5] [6] [2]
Merge[6][2]
[2 3 5] [2 6]
Merge[2 3 5][2 6]
[2 2 3 5 6]
Code Implementation (Java)
package com.coder4j.main.arithmetic.sorting;public class Merge { private static int mark = 0; /** * Merge sort* * @param array * @param low * @param high * @return */ private static int[] sort(int[] array, int low, int high) { int mid = (low + high) / 2; if (low < high) { mark++; System.out.println("Thread in progress" + mark + "subsequent separation, get"); System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]"); // The left array sort(array, low, mid); // The right array sort(array, mid + 1, high); // The left and right merge(array, low, mid, high); } return array; } /** * Merge the array* * @param array * @param low * @param mid * @param high */ private static void merge(int[] array, int low, int mid, int high) { System.out.println("Merge:[" + low + "-" + mid + "] and [" + (mid + 1) + "-" + high + "]"); int[] temp = new int[high - low + 1]; int i = low;// Left pointer int j = mid + 1;// Right pointer int k = 0; // Move the smaller number to the new array first while (i <= mid && j <= high) { if (array[i] < array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } // There may be remaining elements in one of the two arrays// Move the remaining number on the left into the array while (i <= mid) { temp[k++] = array[i++]; } // Move the remaining number on the right into the array while (j <= high) { temp[k++] = array[j++]; } // Overwrite the numbers in the new array array for (int m = 0; m < temp.length; m++) { array[m + low] = temp[m]; } } /** * Merge sort* * @param array * @return */ public static int[] sort(int[] array) { return sort(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("final result"); for (int i : sorted) { System.out.print(i + " "); } }}Test output results:
The first separation is being performed, and the [0-2] [3-4] is being performed, and the second separation is being performed, and the [0-1] [2-2] is being performed, and the third separation is being performed, and the [0-0] [1-1] merge: [0-0] and [1-1] merge: [0-1] and [2-2] are being performed, and the fourth separation is being performed, and the [3-3] [4-4] merge: [3-3] and [4-4] merge: [0-2] and [3-4] final result 2 2 3 5 6
After testing, it is consistent with the results in the example.