Warum Merge Sort des Merge () Funktion hat eine bedingte zweite Schleife?

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

Also, im Grunde ist dies auf meinem Skriptum. Ich finde es ganz allgemein verwirrend, aber ich verstehe den größten Teil davon. Was ich nicht verstehe, ist die Notwendigkeit des "if (j <= low + k - 1)" teil. Es sieht aus wie es überprüft, ob es irgendwelche Elemente „links“ im linken Teil sind. Ist das überhaupt möglich ist, wenn mergesorting?

Answer 1

Wenn zwei sortierten Listen Zusammenführung (nennen wir sie left und right), halten Sie ein Element zu nehmen und es in die result Liste hinzufügen, bis Sie von Elementen in einer Liste der left oder right auslaufen. Dies wird durch die erste while Schleife erfolgt. Nun müssen Sie noch in der linken oder rechten Liste in die Ergebnisliste die Elemente hinzuzufügen. Es gibt zwei Möglichkeiten:

• Die linke Liste ist von Elementen aus, und die rechte Liste hat noch einige. Die Art und Weise der Code hier geschrieben wird, wir brauchen nichts zu tun, da das Ende des Arrays S bereits die letzten Elemente in der right Liste enthält.

• Die rechte Liste ist von Elementen aus, und die linke Liste hat noch einige. Dann kopieren wir die übrigen Elemente bis Ende S. Dies ist, was der if am Ende merge1 den Fall ist.

---

In Bezug auf Ihre Frage, wenn dieser Code ist „schlecht“: Der Code korrekt ist, aber ich würde einige Änderungen vornehmen, um es besser lesbar:

• Beschreibende Variablennamen.
• Passing den Mittelpunkt, die die left und right Listen merge1 trennt anstatt es neu berechnet.