One, the introduction
As we know, generic sort in Java uses merge sort or TimSort. Merge sort runs in O(NlogN) worst time. Next, we analyze the merge sort process and analyze the time complexity of proof. It will also briefly explain why Java chose merge sort as the sorting algorithm for generics.
Diagram merge sort process
- Algorithm idea: Adopt divide-and-conquer method:
- Split: To recursively divide the current sequence into equal halves.
- Integration: The integration of subsequences from the previous step while preserving the order of the elements (merge).
- Merge operation: Refers to the operation of merging two already sorted sequences into a single sequence. Merge sort algorithms rely on merge operations.
- Merge process: take two input arrays A and B and an output array C and three indexes index1,index2 and index3 to the beginning of the three arrays respectively. The smaller of A[index1] and B[index2] is copied to the next position in array C, the relevant index +1. When one array of A and B runs out, copy all the elements in the other array into array C.
Assuming the input array A[1, 7, 9, 13], B[5, 8, 15, 17], the algorithm process is as follows. Compare 1 with 5, 1 is stored in array C; And then 7 is compared to 5, and 5 goes into C.
And then 7 is compared to 8, 7 goes into C; Compare 9 with 8, 8 goes into C.
And then you do that until you compare 13 to 15, and 13 goes into C.
At this point, A has been used up. Copy all the remaining elements in B to C.
As you can see from the figure, merging two sorted tables is linear, making at most n-1 comparisons (you can change the input sequence so that only one number enters array C at a time, except for the last time, when at least two elements enter C). For merge sort, when N=1, it’s obvious; Otherwise, the recursion merges the first half and the second half separately. This is using the idea of divide-and-conquer.
Java implementation merge sort
public class MergeSort {
public static void main(String[] args) {
Integer[] integers = {7.1.13.9.15.5.8.17};
System.out.println("Original sequence:" + Arrays.toString(integers));
mergeSort(integers);
System.out.println("After sorting:" + Arrays.toString(integers));
}
public static <T extends Comparable<? super T>> void mergeSort(T[] a) {
// Because the merge operation is the last line, only a temporary array is required at any time
T[] tmpArray = (T[]) new Comparable[a.length];
mergeSort(a, tmpArray, 0, a.length - 1);
}
private static <T extends Comparable<? super T>> void mergeSort(T[] a, T[] tmpArray, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
/ * *
* Merge left and right data methods
*
* @paramA: Primitive array
* @paramTmpArray: temporary array
* @paramLeftPos: Start subscript on the left
* @paramRightPos: Start subscript on the right
* @paramRightEnd: End subscript on the right
* @param<T> : Element generic
* /
private static <T extends Comparable<? super T>> void merge(T[] a, T[] tmpArray, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Merge operations
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (a[leftPos].compareTo(a[rightPos]) <= 0) {
tmpArray[tmpPos++] = a[leftPos++];
} else {
tmpArray[tmpPos++] = a[rightPos++];
}
}
// Copy the first half
while (leftPos <= leftEnd) {
tmpArray[tmpPos++] = a[leftPos++];
}
// Copy the last half
while (rightPos <= rightEnd) {
tmpArray[tmpPos++] = a[rightPos++];
}
// Write back the original array
for (int i = 0; i < numElements; i++, rightEnd--) {
a[rightEnd] = tmpArray[rightEnd];
}
}
}
Copy the codeMerge sort analysis
We assume that N is a power of 2, and we can always recurse in two parts. For N=1, merge sort takes constant time, O(1). So the time to merge sort for N numbers is equal to the sum of the two parts plus the time to merge. The merge is linear because at most N-1 comparisons are used. The derivation is as follows:
We assumed that N is equal to 2k, and for N not to be a power of 2 (which is usually the case), the result is pretty much the same, just one more step at most.
- Time complexity: It can be seen from the analysis that the best and worst of merge sort are stable at O(NlogN).
- Space complexity: O(N) temporary Spaces are required for merging operations.
- Stability: Stable. Using the idea of divide and conquer, each time merge, the preceding will always be stored in the temporary array first.
Why do Java generics choose merge sort
Merge sort compared to other O(NlogN) sorting algorithms, time is very dependent on the relative overhead of comparison algorithms compared to moving elements in arrays (including temporary arrays). This is contextual. For Java, comparisons can be time-consuming (using a Comparator); But moving elements is a reference assignment, not a copy of a bulky object. The merge algorithm uses the least number of comparisons of all the popular algorithms that use comparisons. Another reason is that merge sort is stable, which is particularly important in some particular scenarios.
Six, summarized
In this paper, the process of merging sort is described in detail by drawing a graph, and the time complexity of merging sort is proved to be stable at O(NlogN) by mathematics. The reason why Java chooses merge sort was briefly discussed. For sorting basic types in Java, quicksort is used.