Example tutorial to implement merge sort algorithm in Java programming

Algorithm overview/ideas
Merge sort is based on a strategy called divide and conquer. The basic idea is this:
1. For two ordered arrays, to combine them into one 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++];
  }
  while (j<=b.length){
    c[k++]=b[j++];
  }
}

It is easy to see that such a merge algorithm is efficient and its time complexity can reach O(n).
2. If there is an unordered array to sort, but its two completely divided subarrays A and B are ordered respectively, we can also easily achieve it with the help of the above code;
3. So, what if A and B are disordered? You can subdivide them into smaller arrays.
4. If such a subarray is divided to the minimum, and each subarray has only one element, it can be regarded as an ordered array.
5. Start with the smallest array, reverse the above steps and merge back into the whole array.
Anyway, merge sort is using recursion, splitting the array into subarrays, and then merging the array.

example
For example, if you want to sort the array a={2,1,3,5,2,3}, divide the array into two subarrays {2,1,3} and {5,2,3}. These subarrays are sorted into {1,2,3} and {2,3,5}. Then merge the two arrays to get the final ordered array. The code is implemented as follows:

void sort(int[] a) {
  int[] aux = new int[a.length];  // Auxiliary 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 sort
In the above implementation, it is equivalent to breaking a big problem into small problems and solving them separately, and then solving the whole big problem with the answers to all the small problems. Sorting a large array into smaller arrays is a top-down sort. There is another implementation of bottom-up sorting, where you merge in pairs, then merge in 44... The code is implemented 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 merging, at the end 1 The second merge is the first 2 Subarrays may be more than first 1 The subarray should be small 
      merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux);
    }
  }
}