Opis sposobu sortowania scalania działa

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

Kod działa, ale mam problem z jego zrozumieniem.

1. Rozumiem cel

   if (hi <= lo) { 
       return; 
   } 
   

   ale nie wiem, co się dzieje, gdy zwrot jest wykonywany.

2. Nie rozumiem, dlaczego ostatni element w funkcji scalania istnieje. Jeśli algorytm się rozdzieli, aż aux jest [3,5] i chcę posortować rosnąco, else if porówna 5 < 3, który przeskoczy do innego i powinien wymienić 2 wartości.

Edycja: odtwarzane nieco z debugera i w tym przykładzie (3 33 1 55 66 34 67 45 23) osiąga funkcję scalania z pierwszych 2 wartości. Ostatni, jeśli porównuje 33 < 3 i wprowadza ostatni. Jeśli te wartości są we właściwej kolejności, jaki jest punkt tego wiersza kodu? Po tablicy [k] = aux [i ++]; wykonywany jest wartość tablica [0] jest taki sam, co jest dziwne, ponieważ AUX [i ++] jest tablica [1]

Answer 1

1. W sposobie sort problem jest podzielona na mniejsze cząstkowych problemów. Gdy zakres do sortowania ma tylko jeden lub zero szerokości, nie ma nic do zrobienia, a metoda może zostać zamknięta. Dzieje się tak, ponieważ tylko jeden element jest sortowany z definicji. Jest to stan zatrzymania rekurencji like m0skit0 said.

2. Elementy nie są zamieniane w tym algorytmie. Metoda próbuje scalić dwie posortowane tablice. Istnieją dwa indeksy: i i j. Gdy i osiągnie środek, wszystkie elementy w prawej części zostaną dodane do tablicy wyników. Jeśli j osiągnie prawą granicę, wszystkie elementy lewej części zostaną dodane do wyniku. To są pierwsze dwa przypadki.
   Teraz w dwóch ostatnich przypadkach algorytm próbuje ustalić, który z bieżących elementów indeksowanych przez i i j jest wartością minimalną i dodaje ją do tablicy wyników. W trzecim przypadku element o numerze j jest mniejszy i dodany do tablicy wyników. W czwartym przypadku wybrano element pod numerem i.