The content is introduced
Introduction to merge sort
When we were at school, the school would hold a sports meeting. There were many events in the sports meeting, such as the long jump. When there are a large number of participants in the long jump competition, all participants are usually divided into multiple groups. Students in each group compete and are ranked according to their scores. Finally, the scores of all students in all groups are summarized to obtain the rankings of all students.
The long jump ranking of all students in the above example is the idea of merge sort. Merge sort is a typical divide-and-conquer algorithm. The Chinese meaning of merge is the meaning of merge, merge sort is divided into two steps: 1. Split up, 2. Merge.
The idea of merge sort
The idea of merging sort is to divide the original data sequence into two sub-sequences of equal size, continue to divide the molecular sequence, until the sub-sequence is in order, merge the divided ordered sub-sequence into a large ordered sequence, and finally merge into an ordered sequence.
Merge sort animation demonstration
Merge sort analysis
In general, there is no special requirement for sorting algorithms to sort in ascending order, small first, big last. The array consists of {7, 3, 1, 9, 5, 2, 8, 6}.
Merge sort is divided into two steps: 1. Split, 2. Merge.
- Break up
When sorting an array of {7, 3, 1, 9, 5, 2, 8, 6}, merge sort first splits the array in half.
And then figure out how to sort the array on the left, sort the array on the right, and merge them. Obviously, the left and right arrays are still unordered, and then split the left array in half and the right array in half, as follows:
Now each subarray is of length 2, and each subarray is still unordered.
The result is as shown in the figure above. After this split, the length of each subarray is 1, and we consider the subarray of length 1 to be ordered. I don’t need to split it anymore. That’s the end of the split.
- A merger. So now each subarray has length 1, so it’s an ordered subarray, so you have to merge two of length 1 into an ordered array of length 2.
The animation looks like this:
So far each of these subarrays has length 2, so they’re ordered subarrays, so we need to merge two of them into an ordered array of length 4.
The animation looks like this:
So now each of these subarrays is 4 in length, so it’s an ordered subarray, and you need to merge two of these 4 in length into an ordered array of length 8.
The animation looks like this:
Merge sort Details at merge time
When merge sort is used to merge ordered subarrays into larger ordered arrays, you need to compare the two subarrays and take the smaller element.
- If the element on the left is greater than the element on the right, take the smaller element on the right.
- If the element on the right is greater than or equal to the element on the left, take the smaller element on the left.
The above two cases are common, and there are two special cases to be aware of:
- Everything on the left is pre-evaluated, and everything on the right is directly assigned
- Everything on the right hand side is pre-evaluated, and everything on the left hand side is directly assigned
Merge sort code
The code is as follows:
public class MergeSortTest2 {
public static void main(String[] args) {
int[] arr = new int[] {7.3.1.9.5.2.8.6};
mergeSort(arr);
}
// Merge sort method
public static void mergeSort(int[] arr) {
// Use an extra array of the same size as the array to be sorted
int[] aux = new int[arr.length];
mergePass(arr, 0, arr.length - 1, aux);
// mergePass2(arr, 0, arr.length - 1, aux);
}
// Merge sort on arR array [low, hight]
private static void mergePass(int[] arr, int low, int high, int[] aux) {
// The end condition of the recursion, when the small index and the large index are the same, i.e. the end of the split element
if (low >= high)
return;
// Split an array into two arrays
int mid = (low + high) / 2;
mergePass(arr, low, mid, aux);
mergePass(arr, mid + 1, high, aux);
// Sort the two arrays
merge(arr, low, mid, high, aux);
}
// Merge arr[mid+1, high] and arr[mid+1, high]
private static void merge(int[] arr, int low, int mid, int high, int[] aux) {
// The contents of a temporary array are the contents of two arrays to be sorted. The sorted contents are placed in the ARR
for (int k = low; k <= high; k++) {
aux[k] = arr[k];
}
// I is the index of the left array
// j is the index of the array on the right
int i = low;
int j = mid + 1;
// Iterate over the left and right decimal combinations into a large array
for (int k = low; k <= high; k++) {
if (i > mid) {
// All the values on the left are pre-selected, and all the values on the right are directly assigned
arr[k] = aux[j];
j++;
} else if (j > high) {
// All the values on the right side are pre-selected, and the left side is directly assigned
arr[k] = aux[i];
i++;
} else if (aux[i] > aux[j]) {
// The element in the left array is greater than the element in the right array
arr[k] = aux[j];
j++;
} else { // aux[left] <= aux[right]
// The element in the right array is greater than or equal to the element in the left array
arr[k] = aux[i];
i++;
}
}
}
}
Copy the codeMerge sort code optimization 1
Merge sort code optimization 1, switch to insert sort for small data size.
If the amount of data to be sorted is large, when the subarray split ratio is small, it can be changed to insert sort, because the efficiency of insert sort is very high when the data size is small. This optimization method can improve the performance of most recursive sorting algorithms.
The optimized code is as follows:
public class MergeSortTest2 {
public static void main(String[] args) {
int[] arr = new int[] {7.3.1.9.5.2.8.6};
mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr) {
// Use an extra array of the same size as the array to be sorted
int[] aux = new int[arr.length];
mergePass2(arr, 0, arr.length - 1, aux);
}
// optimization: Use insertion sort for small subarrays
// Merge sort on arR array [low, hight]
private static void mergePass2(int[] arr, int low, int high, int[] aux) {
if (low >= high) return;
// Use insertion sort on small subarrays
if (high - low <= 15) {
insertionSort(arr, low, high);
}
// Split an array into two arrays for sorting
int mid = (low + high) / 2;
mergePass2(arr, low, mid, aux);
mergePass2(arr, mid + 1, high, aux);
// Sort the two arrays
merge(arr, low, mid, high, aux);
}
// Insert sort is used on elements of an array whose index range is specified
public static void insertionSort(int[] arr, int low, int high) {
for (int i = low + 1; i < high; i++) {
int e = arr[i]; // Get the current element to insert
int j;
for (j = i; j > 0 && arr[j-1] > e; j--) {
arr[j] = arr[j-1];
}
arr[j] = e;
}
}
// Merge arr[mid+1, high] and arr[mid+1, high]
private static void merge(int[] arr, int low, int mid, int high, int[] aux) {
// The contents of a temporary array are the contents of two arrays to be sorted. The sorted contents are placed in the ARR
for (int k = low; k <= high; k++) {
aux[k] = arr[k];
}
// I is the index of the left array
// j is the index of the array on the right
int i = low;
int j = mid + 1;
// Iterate over the left and right decimal combinations into a large array
for (int k = low; k <= high; k++) {
if (i > mid) {
// All the values on the left are pre-selected, and all the values on the right are directly assigned
arr[k] = aux[j];
j++;
} else if (j > high) {
// All the values on the right side are pre-selected, and the left side is directly assigned
arr[k] = aux[i];
i++;
} else if (aux[i] > aux[j]) {
// The element in the left array is greater than the element in the right array
arr[k] = aux[j];
j++;
} else { // aux[left] <= aux[right]
// The element in the right array is greater than or equal to the element in the left array
arr[k] = aux[i];
i++;
}
}
}
}
Copy the codeMerge sort code optimization 2
Merge sort uses recursion to sort, which is relatively clear and easy to understand in code writing and reading. However, when there is a large amount of data to be sorted, recursion can cause performance loss in time and space, and may cause stack overflow. What we’re looking for in sorting is efficiency, so we can turn recursion into iteration, which is bottom-up merge sort. To improve the performance of merge sort.
Bottom-up merge sort can be divided into two processes:
- Merge sort: start from subsequence length 1 and merge sort in pairs to get ordered large sequence of 2 times length.
- Loop: The subsequence starts at 1, and the loop doubles the length of the subsequence, continuing to merge and sort.
The bottom-up merge sort animation looks like this:
The bottom-up merge sort code is as follows:
public class BottomUpMergeSortTest2 {
public static void main(String[] args) {
int[] arr = new int[] {7.3.1.9.5.2.8.6};
mergeSortBottomUp(arr);
System.out.println(Arrays.toString(arr));
}
// Do not use recursive, bottom-up merge sort
public static void mergeSortBottomUp(int[] arr) {
// Use an extra array of the same size as the array to be sorted
int[] aux = new int[arr.length];
// Split the array in the for loop
// size is the length of the subarray
for (int size = 1; size < arr.length; size += size) { // size = 1, 2, 4
for (int low = 0; low < arr.length -size; low += size+size) {
// Optimization: If the last element of the left subarray is greater than the minimum value of the right subarray, sort is required
if (arr[low+size-1] > arr[low+size]) {
merge(arr, low, low + size -1, Math.min(low + size + size - 1, arr.length - 1), aux);
}
}
}
}
// Merge arr[mid+1, high] and arr[mid+1, high]
private static void merge(int[] arr, int low, int mid, int high, int[] aux) {
// The contents of a temporary array are the contents of two arrays to be sorted. The sorted contents are placed in the ARR
for (int k = low; k <= high; k++) {
aux[k] = arr[k];
}
// I is the index of the left array
// j is the index of the array on the right
int i = low;
int j = mid + 1;
// Iterate over the left and right decimal combinations into a large array
for (int k = low; k <= high; k++) {
if (i > mid) {
// All the values on the left are pre-selected, and all the values on the right are directly assigned
arr[k] = aux[j];
j++;
} else if (j > high) {
// All the values on the right side are pre-selected, and the left side is directly assigned
arr[k] = aux[i];
i++;
} else if (aux[i] > aux[j]) {
// The element in the left array is greater than the element in the right array
arr[k] = aux[j];
j++;
} else { // aux[left] <= aux[right]
// The element in the right array is greater than or equal to the element in the left array
arr[k] = aux[i];
i++;
}
}
}
}
Copy the codeThe bottom-up merge sort avoids the stack space with the depth of log2n in recursion, and uses the same size of AUX array as the original array, so the space complexity is 0(n), and avoids the improvement of recursion in time performance. Therefore, non-recursive methods are given priority when merge sort is used.
Merge sort complexity
The time complexity of merge sort can be seen in the following figure:
Merge sort will split the data of size N
N times, so the total time is zero
Complexity: The space complexity of merge sort is O(n) because a secondary array of the same size as the original array is used during merge sort.
conclusion
- The idea of merging sort is to divide the original data sequence into two sub-sequences of equal size, continue to divide the molecular sequence, until the sub-sequence is in order, merge the divided ordered sub-sequence into a large ordered sequence, and finally merge into an ordered sequence. Merge sort is divided into two steps: 1. Split, 2. Merge.
- Merge sort code optimization 1, switch to insert sort for small data size.
- Merge sort from bottom up to avoid the extra cost of recursive time and space.
———- End ———-
Original articles and animation production is really not easy, your thumbs up is the biggest support!
For more articles, please pay attention to wechat public number: Cousin Animation learning programming