CODEWITHSUNDEEP
pythonmergesort
Major Despard
Major Despard

Reputation: 95

MERGESORT never reaches the second array/list

Here's the algorithm I'm trying to follow, from the CLSR book:

enter image description here

And here's my code in Python:

#merge sort

def merge_sort(A, p, q, r):
    n_prime = q - p + 1
    n_second = r - q
    L = [x for x in range(n_prime + 1)]
    R = [y for y in range(n_second + 1)]

    for i in range(n_prime):
        L[i] = A[p + i - 1]

    for j in range(n_second):
        R[j] = A[q + j]

    L[n_prime] = float("inf")
    R[n_second] = float("inf")

    i = 0
    j = 0

    for k in range(p, r):
        if L[i] <= R[i]:
            A[k] = L[i]
            i += 1
        elif A[k] = R[j]:
            j += 1

    return A



A = [2, 4, 5, 7, 8, 6, 9, 1]

print(merge_sort(A, 0, 3, 7))

All the rest of the code works fine. According to VSCode Debugger, L and R are created without a hitch, but then in the last loop invariant, there's a problem: It never enumerates j. The elif condition is never met, so it never reaches the second list.

What's wrong with my implementation of the algorithm? I bet it has something to do with the fact that this book's arrays start with 1, but python list's indices start with 0. Why did they do this? Is there a general rule I should follow in translating the algorithms?

Thanks.

Upvotes: 0

Views: 99

Answers (3)

rcgldr
rcgldr

Reputation: 28826

This is the second time I've seen the CLSR version in the last week. I don't like the idea of using "sentinel values" (infinity) to avoid bounds checking on indexes, as it doesn't take that much more code, and won't work if A[] is an array of integers and already includes maximum values. The code has to be modified since the CLSR index range for arrays is 1 to n as opposed to 0 to n-1.

Here is example code that does a bounds check after each move, and if the end of a sub-run is reached, it appends the remainder of the remaining sub-run. Also the input parameters are beg (first index of run) and end (1 + last index of run), similar to C++ std::vector::begin() and std::vector::end(), which is the typical usage for merge sort.

def mergesort(a,beg,end):
    if (end-beg) > 1:
        mid=(beg+end)//2
        mergesort(a,beg,mid)
        mergesort(a,mid,end)
        merge(a,beg,mid,end)
def merge(a,beg,mid,end):
    left = a[beg:mid]
    right = a[mid:end]
    i = 0
    j = 0
    k = beg   
    while True:
        if left[i] <= right[j]:
            a[k] = left[i]
            i += 1
            k += 1
            if(i < len(left)):
                continue
            a[k:end] = right[j:len(right)]
            break
        else:
            a[k] = right[j]
            j += 1
            k += 1
            if(j < len(right)):
                continue
            a[k:end] = left[i:len(left)]
            break
....
mergesort(a,0,len(a))   #call to merge sort to sort a[]

This is not an optimal implementation. It would be better to do a one time allocation of a working array, rather than allocating two working sub-arrays at each merge, and alternate the direction of merge with each level of recursion (or if doing bottom up merge sort, with each pass), to avoid copying data.

Upvotes: 0

Yishai E
Yishai E

Reputation: 521

Probably should be elif A[k] == R[j] (two "=" signs), what you wrote is an assignment.

I think I found the issue: it should be if L[i]<=R[j], not R[i].

Code that ran for me: 

#merge sort
def merge_sort(A, p, q, r):
    n_prime = q - p + 1
    n_second = r - q
    L = [x for x in range(n_prime + 1)]
    R = [y for y in range(n_second + 1)]
    for i in range(n_prime):
        L[i] = A[p + i - 1]
    for j in range(n_second):
        R[j] = A[q + j]
    L[n_prime] = float("inf")
    R[n_second] = float("inf")
    i = 0
    j = 0
    print("L:", len(L), ", R:", len(R))
    for k in range(p, r):
        if L[i] <= R[j]:
            print("if", i)
            print(L[i])
            print(R[i])
            A[k] = L[i]
            i += 1
        else: 
            print("else", k, j, A[k], R[j])
            A[k] = R[j]
            j += 1
    return A

}

Upvotes: 1

user11321561
user11321561

Reputation: 11

You wrote:

elif A[k] = R[j]:
    j += 1

when the algorithm says:

else:
    A[k] = R[j]
    j += 1

A typo here will result in an "array index out of bounds" error:

if L[i] <= R[i]:

You likely meant:

if L[i] <= R[j]:

What's wrong with my implementation of the algorithm?

It's incomplete; you only implemented the merge procedure, not the entire mergesort algorithm. Hence, running your code with the above corrections will output a partially sorted list.

Upvotes: 0

Related Questions