This article has been accepted by Github github.com/silently952…

IDEA plug-ins commonly used by programmers: github.com/silently952…

Fully open source Taoke project: github.com/silently952…

Wechat official account: Beta learning Java

preface

In the last article, “Common primary sorting algorithms, This time all understand”, mainly talked about the common primary sorting algorithms, these algorithms are O(n²) time complexity, these algorithms can not handle a large amount of data; In this article we will talk about an algorithm that completes sorting based on merge operations.

Merge sort algorithm idea

To sort an array, you divide it into two arrays, sort it separately, and then merge it together, and repeat the recursive process until the array is sorted, and that’s how merge sort works.

The advantage of merge sort is that it guarantees that the sorting time of any array of length N is proportional to NlogN, and this advantage cannot be achieved by elementary sort.

The disadvantage is that merging requires an extra array, the extra space is proportional to N

In-place merge is implemented

Before merging sort, we need to merge two ordered arrays, that is, merge two ordered arrays into one ordered array;

  • In this process we need to introduce an auxiliary array;
  • Merge (a, lo, mid, hi). Merge (a, LO, mid, hi) merges arrays A [lo..mid] and A [mid..hi] into an ordered array.
  • The public functions from the previous article are needed in this methodless, refer to the previous article “Common elementary sorting algorithms, This time all understand”
public class MergeSort implements SortTemplate { private Comparable[] aux; Public void sort(Comparable[] array) {private void sort(Comparable[] a, int lo, int mid, int hi) { for (int i = lo; i <= hi; i++) { aux[i] = a[i]; } int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j++]; } else if (j > hi) { a[k] = aux[i++]; } else if (less(aux[i], aux[j])) { a[k] = aux[i++]; } else { a[k] = aux[j++]; }}}}Copy the code

Top down merge sort

Based on the idea of divide-and-conquer, a large array is sorted recursively into smaller arrays, which are sorted and then merged until the entire array is sorted. This operation is called top-down merge sort

public class MergeSort implements SortTemplate { private Comparable[] aux; @Override public void sort(Comparable[] array) { aux = new Comparable[array.length]; doSort(array, 0, array.length - 1); } private void doSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } int mid = (hi - lo) / 2 + lo; doSort(array, lo, mid); doSort(array, mid + 1, hi); merge(array, lo, mid, hi); } private void merge(Comparable[] a, int mid, int hi) {// ellipsis}}Copy the code

The above code is a standard recursive merge sort operation, but after careful consideration, the algorithm can be optimized

  1. Test whether the array is already in order; If a[mid]<=a[mid+1], then we can skip the merge method. Fixed doSort method
private void doSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } int mid = (hi - lo) / 2 + lo; doSort(array, lo, mid); doSort(array, mid + 1, hi); if (array[mid].compareTo(array[mid + 1]) >= 0) { merge(array, lo, mid, hi); }}Copy the code
  1. For small arrays you can do insertion sort; Using merge sort for small arrays increases the recursive call stack, so we can consider using insert sort to handle sorting of subarrays
private void doSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } if (hi-lo < 5) {insertionSort(array, lo, hi); return; } int mid = (hi - lo) / 2 + lo; doSort(array, lo, mid); doSort(array, mid + 1, hi); if (less(array[mid + 1], array[mid])) { merge(array, lo, mid, hi); Private void insertionSort(Comparable[] array, int lo, int hi) {for (int I = lo; i <= hi; i++) { for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); }}}Copy the code
  1. Saves time copying elements into auxiliary arrays; This is cumbersome and requires switching the roles of input data and output arrays at each level of recursion; The complete code after modification is as follows:
public class MergeSort implements SortTemplate { private Comparable[] aux; @Override public void sort(Comparable[] array) { aux = array.clone(); doSort(aux, array, 0, array.length - 1); } private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) { if (lo >= hi) { return; } if (hi-lo < 5) {insertionSort(dest, lo, hi); return; } int mid = (hi - lo) / 2 + lo; doSort(dest, src, lo, mid); doSort(dest, src, mid + 1, hi); if (less(src[mid + 1], src[mid])) { merge(src, dest, lo, mid, hi); Private void insertionSort(Comparable[] array, int lo, int hi) {for (int I = lo; i <= hi; i++) { for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); } } } private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { dest[k] = src[j++]; } else if (j > hi) { dest[k] = src[i++]; } else if (less(src[i], src[j])) { dest[k] = src[i++]; } else { dest[k] = src[j++]; }}}}Copy the code

Each level of recursion will order the subarray, but the subarray may be aux[lo..hi] or a[lo..hi]; SRC =aux, dest=array; SRC =aux, dest=array

Bottom up merge sort

Another way to do merge is to merge the smaller arrays first, and then merge the subarrays in pairs until the whole array is sorted

public class MergeSort implements SortTemplate { private Comparable[] aux; @Override public void sort(Comparable[] array) { int length = array.length; aux = new Comparable[length]; for (int sz = 1; sz < length; sz += sz) { for (int i = 0; i < length - sz; i += 2 * sz) { merge(array, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1)); } } } private void merge(Comparable[] a, int lo, int mid, int hi) { for (int i = lo; i <= hi; i++) { aux[i] = a[i]; } int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j++]; } else if (j > hi) { a[k] = aux[i++]; } else if (less(aux[i], aux[j])) { a[k] = aux[i++]; } else { a[k] = aux[j++]; }}}}Copy the code

Finally (pay attention, don’t get lost)

There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.

Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏

All source code has been put into github repository github.com/silently952…