Is this a bad version of the Merge Sort algorithm?

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

So, basically, this is on my lecture notes. I find it quite confusing in general but I understand the biggest part of it. What I don't understand is the need of the "if (j <= low + k - 1)" part. It looks like it checks if there are any elements "left" in the left part. Is that even possible when mergesorting?

Answer 1

When merging two sorted lists (let's call them left and right), you keep taking one item and adding it to the result list, until you run out of items in either the left or right list. This is done by the first while loop. Now you need to add the elements remaining in the left or right list to the result list. There are two options:

• The left list is out of elements, and the right list still has some. The way the code is written here, we don't need to do anything, since the end of the S array already contains the last elements in the right list.

• The right list is out of elements, and the left list still has some. Then we copy the remaining elements to the end of S. This is what the if at the end of merge1 does.

---

Regarding your question if this code is "bad": The code is correct, but I would make some changes to make it more readable:

• Descriptive variable names.
• Passing the midpoint which separates the left and right lists to merge1 instead of having it recalculated.