Perché la funzione di () Merge Merge Sort di avere un secondo ciclo condizionale?

Question

merge1(int low, int high, int S[], U[]) 
{ 
    int k = (high - low + 1)/2
    for q (from low to high) U[q] = S[q]
    int j = low 
    int p = low 
    int i = low + k 

    while (j <= low + k - 1) and (i <= high) do 
    { 
        if ( U[j] <= U[i] ) 
        {
            S[p] := U[j] 
            j := j+1
        } 
        else 
        { 
            S[p] := U[i] 
            i := i+1 
        } 
        p := p+1 
    } 

    if (j <= low + k - 1) 
    { 
        for q from p to high do 
        { 
            S[q] := U[j] 
            j := j+1 
        } 
    }
}


merge_sort1(int low, int high, int S[], U[]) 
{ 
    if low < high 
    { 
        int k := (high - low + 1)/2 
        merge_sort1(low, low+k-1, S, U) 
        merge_sort1(low+k, high, S, U) 
        merge1(low, high, S, U) 
    } 
}

Quindi, in sostanza, questo è il mio dispense. Trovo molto confusa in generale, ma ho capito la più grande parte di essa. Quello che non capisco è il bisogno del "if (j <= basso + k - 1)" parte. Sembra che controlli se ci sono elementi "sinistra" nella parte sinistra. È che anche possibile quando mergesorting?

Answer 1

Quando la fusione di due liste ordinate (chiamiamoli così left e right), si continua a prendere un elemento e aggiungendolo alla lista result, fino ad esaurimento delle voci sia nella left o l'elenco right. Questo viene fatto il primo ciclo while. Ora è necessario aggiungere i restanti elementi nella lista di sinistra o destra per la lista dei risultati. Ci sono due opzioni:

• La lista di sinistra è fuori di elementi, e la lista di destra ha ancora un po '. Il modo in cui il codice è scritto qui, non abbiamo bisogno di fare nulla, dal momento che la fine della matrice S contiene già gli ultimi elementi della lista right.

• La lista di destra è fuori di elementi, e la lista di sinistra ha ancora qualche. Poi copiamo gli elementi rimanenti alla fine del S. Questo è ciò che il if alla fine del merge1 fa.

---

Per quanto riguarda la tua domanda se questo codice è "cattivo": il codice è corretto, ma vorrei fare alcune modifiche per renderlo più leggibile:

• I nomi delle variabili descrittiva.
• Passando il punto centrale che separa le liste left e right a merge1 invece di avere ricalcolato.