Understanding how merge sort works

Question

private void merge(int[] array, int[] aux, int low, int mid, int hi) { int i = low, j = mid + 1, k; for (k = low; k <= hi; k++) { aux[k] = array[k]; } for (k = low; k <= hi; k++) { if (i > mid) { array[k] = aux[j++]; } else if (j > hi) { array[k] = aux[i++]; } else if (aux[j] < aux[i]) { array[k] = aux[j++]; } else /* if (aux[i] <= aux[j] */ { array[k] = aux[i++]; } } } private void sort(int[] array, int[] aux, int lo, int hi) { if (hi <= lo) { return; } int mid = lo + (hi - lo) / 2; sort(array, aux, lo, mid); sort(array, aux, mid + 1, hi); merge(array, aux, lo, mid, hi); } public void mergeSort() { int aux[] = new int[n]; sort(ar, aux, 0, n - 1); } 

The code works, but it's hard for me to understand it.

• I understand the purpose

   if (hi <= lo) { return; } 

  but I don’t know what will happen when the refund is made.

• I do not understand why the latter exists in the merge function. If the algorithm crashes until aux is [3,5] , and I want to sort in ascending order, else if will compare 5 < 3 , which will go to another, and it should exchange 2 values.

Edit: I played a little with the debugger, and for this example (3 33 1 55 66 34 67 45 23) it reaches the merge function with the first two values. The latter, if compares 33 <3 and is included in the latter. If these values ​​are in the correct order, what is the point of this line of code? After array [k] = aux [i ++]; the value of array [0] is executed - this is the same as odd, because aux [i ++] is an array [1]

Answer 1

• In the sort method, the problem is divided into smaller sub-problems. When the range for sorting is only one or zero width, there is nothing to do, and the method can be closed. This is because one item is sorted by definition. This is the condition for stopping recursion as specified in m0skit0 .

• Elements are not replaced in this algorithm. The method tries to combine two sorted arrays. There are two indices i and j . When i reaches the middle, all the elements on the right side are added to the result array. If j reaches the right border, all elements of the left side are added to the result. These are the first two cases.
  Now, in the last two cases, the algorithm tries to find out which of the current elements indexed by i and j is minimal and adds it to the results array. In the third case, the element at j smaller and is added to the array of results. In the fourth case, the element at i is selected.