Comprendere come funziona l'ordinamento merge

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); 
} 

Il codice funziona ma ho difficoltà a capirlo.

1. capisco lo scopo di

   if (hi <= lo) { 
       return; 
   } 
   

   ma non so cosa succede quando viene eseguito il ritorno.

2. Non capisco perché esista l'ultima funzione di unione. Se l'algoritmo si divide fino al aux è [3,5] e voglio ordinare in ordine crescente, lo else if confronterà con lo 5 < 3 che passerà al resto e dovrebbe scambiare i 2 valori.

Edit: ho giocato un po 'con il debugger e per questo esempio (3 33 1 55 66 34 67 45 23) raggiunge la funzione di unione con i primi 2 valori. L'ultimo altro se confronta 33 < 3 e inserisce l'ultimo altro. Se questi valori sono nell'ordine corretto, qual è il punto di questa linea di codice? Dopo array [k] = aux [i ++]; viene eseguito il valore della matrice [0] è la stessa che è dispari perché aux [i ++] è array [1]

Answer 1

1. Nel metodo sort il problema è suddivisa in piccoli sotto-problemi. Quando l'intervallo da ordinare è solo uno o zero, non c'è nulla da fare e il metodo può essere chiuso. Questo perché un solo elemento è ordinato per definizione. È la condizione di arresto della ricorsione like m0skit0 said.

2. Gli elementi non vengono scambiati in questo algoritmo. Il metodo recupera per unire due array ordinati. Ci sono due indici i e j. Quando i raggiunge il centro, tutti gli elementi nella parte destra vengono aggiunti all'array dei risultati. Se j raggiunge il bordo destro, tutti gli elementi della parte sinistra vengono aggiunti al risultato. Questi sono i primi due casi.
   Ora negli ultimi due casi l'algoritmo tenta di determinare quale degli elementi correnti indicizzati da i e j è il minimo e lo aggiunge all'array dei risultati. Nel terzo caso l'elemento a j è più piccolo e aggiunto alla matrice di risultati. Nel quarto caso è selezionato l'elemento i.