python - How do I fix an out of index error in a 3 way merge sort?

Question

I am currently writing a 3 way merge sort algorithm in python and have stumbled upon a list index out of range error when I run my code.

def merge_sort_algorithm(sort_list):
    
    if len(sort_list) < 2:
        return(sort_list)

    third = int(len(sort_list)/3)
    two_thirds = third * 2
    left = sort_list[:third]
    mid = sort_list[third:two_thirds]
    right = sort_list[two_thirds:]

    merge_sort_algorithm(left)
    merge_sort_algorithm(mid)
    merge_sort_algorithm(right)

    i = 0 #left
    j = 0 #mid
    k = 0 #right

    l = 0

    while i < len(left) and j < len(mid) and k < len(right) :
        if (left[i] < right[k] and left[i] < mid[j]):
            sort_list[l] = left[i]
            i += 1
        elif (mid[j] < left[l] and mid[j] < right[k]):
            sort_list[l] = mid[j]
            j += 1
        else:
            l += 1
    
    while i < len(left) and j < len(mid):
        if (left[i] < mid[j]):
            sort_list[l] = left[i]
            i += 1
        else:
            sort_list[l] = mid[j]
            j += 1

    while i < len(left) and k < len(right):
        if (left[i] < right[k]):
            sort_list[l] = left[i]
            i += 1
        else:
            sort_list[l] = right[k]
            k += 1

    while j < len(mid) and k < len(right):
        if (mid[j] < right[k]):
            sort_list[l] = mid[j]
            j += 1
        else:
            sort_list[l] = right[k]
            k += 1
    
    while i < len(left):
        sort_list[l] = left[i]
        i += 1
    
    while j < len(mid):
        sort_list[l] = mid[j]
        j += 1
    
    while k < len(right):
        sort_list[l] = right[k]
        k += 1

When the algorithm uses recursion to go to the elif statement elif (mid[j] < left[l] and mid[j] < right[k])

It gives me an error. I tried using a debugger but I'm not sure what I am doing wrong. Any help would be appreciated, thanks.

question from:https://stackoverflow.com/questions/65841473/how-do-i-fix-an-out-of-index-error-in-a-3-way-merge-sort

Answer 1

mid[j] < left[l] should be mid[j] < left[i]