Sorting Algorithms:Merge Sort
preface
The blog used for the weak chicken review consolidation, lay a solid foundation, but also hope that the big guy is generous to give advice.
The basic idea
Merge sort (two-way merge sort) using recursion and divide-and-conquer, the original sequence is divided into two sub-sequences from the middle, the segmented sub-sequence is repeated, and finally the segmented sub-sequence is sorted to form a new sub-sequence, and then the sub-sequence is combined to form a well-ordered new sequence.
Dynamic figure sample
Algorithm complexity analysis
| On average, | The worst | The best | The stability of | Spatial complexity |
|---|---|---|---|---|
| O(nlogn) | O(nlogn) | O(nlogn) | stable | O(n+logn) |
P.S. n elements are traversed to ensure that they are placed in newArray, and all records in the sequence to be sorted are scanned, so O(n). From the complete binary tree, we know that the whole merge sort needs log2n times, so best = worst = average =O(n*logn). Since merge sort requires the same amount of storage space as the original record sequence to store the merge result and the stack space of log2N in recursion, the space complexity is O(n+logn).
Code implementation
import java.util.Arrays;
import java.util.Random;
/ * *
* MergingSort
* Merge sort (two-way merge sort)
* Split the original sequence into two subsequences using recursion and divide-and-conquer,
* Repeat the operation on the segmented subsequence,
* Finally, the split sub-sequence is sorted to form a new sub-sequence, and then the sub-sequence is merged
* Form a sorted new sequence
* Time complexity analysis
* all n elements have to be iterated to make sure they're placed in newArray,
* Need to scan all records in the sequence to be sorted, O(n)
* from the complete binary tree, we know that the whole merge sort needs log2n times
* So best = worst = average =O(n*logn)
* Since merge sort requires the same amount of storage space as the original sequence of records to store the merge result and the log2n stack space for recursion,
* Space complexity O(n+logn)
* Stability and stability
* /
public class MergingSort {
public static void main(String[] args) {
int[] a = new int[10];
boolean flag = true;
//random array
for (int i = 0; i < a.length; i++) {
Random rd = new Random();
a[i] = rd.nextInt(10);
}
System.out.println("Random Array :");
System.out.println(Arrays.toString(a));
System.out.println();
System.out.println("Merging Sort :");
// merge sort starts
mergingSort(a, a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
// Recursive method to achieve sequence segmentation and merge
// Pass in the sequence to be sorted, the new sequence to be generated, the beginning and end of the sequence
public static void mergingSort(int[] oldArray, int[] newArray, int start, int end) {
// Define the value to split the sequence down the middle
int mid;
// Define a temporary array to hold the split array
int[] tempArray = new int[oldArray.length];
// If the array horn == tail horn, then only one element is waiting for the sequence, the new sequence is the old sequence
// At the end of the recursion, the sequence must be split into individual elements
if (start == end) {
newArray[start] = oldArray[start];
} else {
/ / get the median
mid = (start + end) / 2;
// Split the sequence separately
mergingSort(oldArray, tempArray, start, mid);
mergingSort(oldArray, tempArray, mid + 1, end);
// Sort and merge the partitioned sequences
merge(tempArray, newArray, start, mid, end);
}
}
public static void merge(int[] tempArray, int[] newArray, int start, int mid, int end) {
int j, k, l;
// We know that each sequence is split into two sequences, left and right
// Start with the smallest corner in the left and right sequences and compare them
for (j = mid + 1, k = start; start <= mid && j <= end; k++) {
// Temp [I] to temp[mid] temp[mid+1] to temp[end
// If the current element in the left sequence is small, put the current element in the new sequence first
// The element comparison code shows that it is stable
if (tempArray[start] < tempArray[j]) {
newArray[k] = tempArray[start++];
} else {
newArray[k] = tempArray[j++];
}
}
// After the last operation, the left or right sequence may have a surplus, continue to add the remaining elements to the new sequence
if (start <= mid) {
for (l = 0; l <= mid - start; l++) {
newArray[k + l] = tempArray[start + l];
}
}
if (j <= end) {
for (l = 0; l <= end - j; l++) {
newArray[k + l] = tempArray[j + l];
}
}
}
}
Copy the codereference
GeeksforGeeks：https://www.geeksforgeeks.org/merge-sort/
Top ten classic sorting algorithms: https://www.cnblogs.com/onepixel/articles/7674659.html
Dahua data structure “: https://book.douban.com/subject/6424904/