Algorithm overview/ideas
Merge sorting is based on a strategy called "divide and conquer". The basic idea is as follows:
1. For two ordered arrays, to merge them into an ordered array, we can easily write the following code:
//both a and b is ascend.public void merge(int[] a, int[] b, int[] c){ int i=0,j=0,k=0; while (i<=a.length && j<=b.length){ if (a[i]<=b[i]){ c[k++]=a[i++]; } else{ c[k++]=b[j++]; } } while (i<=a.length){ c[k++]=a[i++]; }} It is easy to see that such a merging algorithm is efficient and its time complexity can reach O(n).
2. If there is an unordered array that needs to be sorted, but its two completely divided subarrays A and B are ordered separately, we can also easily implement them with the help of the above code;
3. So, what should I do if A and B are disordered? You can split them into smaller arrays.
4. If you divide it all the way to the smallest, each subarray has only one element, it can be regarded as an ordered array.
5. Start with these smallest arrays, merge them against the above steps, and the entire array is arranged.
In short, merge sorting is to use recursion, first decompose the array into a subarray, and then merge the array.
example
Here is an example. If you want to sort the array a={2,1,3,5,2,3}, then divide the array into two subarrays: {2,1,3} and {5,2,3}. After sorting these two subarrays, they become {1,2,3} and {2,3,5}, and then merge the two arrays to obtain the final ordered array. The code implementation is as follows:
void sort(int[] a) { int[] aux = new int[a.length]; //Aux array mergeSort(a, 0, a.length - 1, aux);}void mergeSort(int[] a, int lo, int hi, int[] aux) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; mergeSort(a, lo, mid, aux); mergeSort(a, mid + 1, hi, aux); merge(a, lo, mid, hi, aux);}void merge(int[] a, int lo, int mid, int hi, int[] aux) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (aux[i] <= aux[j]) a[k] = aux[i++]; else a[k] = aux[j++]; }} Another implementation: bottom-up merge sorting
In the above implementation, it is equivalent to splitting a big problem into small problems and solving them separately, and then using the answers to all small problems to solve the entire big problem. Dividing the sort of a large array into a small array The sort of sort is a top-down sort. There is another implementation that is bottom-up sorting, that is, first merge two and then merge four and four... The code implementation is as follows:
void sort(int[] a) { int N = a.length; int[] aux = new int[N]; for (int sz = 1; sz < N; sz += sz) { for (int lo = 0; lo < N - sz; lo += sz + sz) { //In each round of merge, the second sub-array that was merged the last time may be smaller than the first sub-array merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux); } }}