[FIXED] Finding out the middle point in mergesort in Python

Issue

I have written two different implementations of mergesort algo with only one difference, that of formula used in finding the middle point of the array to divide it.

First implementation : (Runs correctly)

def mergesort(arr):
    start = 0
    end = len(arr) - 1
    if len(arr) > 1:
        mid = int(len(arr)/2)
        left = mergesort(arr[:mid])
        right = mergesort(arr[mid:])
        return merge(left,right)
    else:
        return arr

def merge(left,right):
    final = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                final.append(left[0])
                del left[0]
            elif right[0] < left[0]:
                final.append(right[0])
                del right[0]
        elif len(right) > 0:
            final.extend(right)
            right = []
        elif len(left) > 0:
            final.extend(left)
            left = []
    return final


arr = list(map(int,input().split(' ')))
print ("List before sorting:",arr)
final = mergesort(arr)
print ("After sorting:",final)

Second implementation (Gets into an infinite loop):

def mergesort(arr):
    start = 0
    end = len(arr) - 1
    if len(arr) > 1:
        mid = int(start + (end - start)/2)
        left = mergesort(arr[:mid])
        right = mergesort(arr[mid:])
        return merge(left,right)
    else:
        return arr

def merge(left,right):
    final = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                final.append(left[0])
                del left[0]
            elif right[0] < left[0]:
                final.append(right[0])
                del right[0]
        elif len(right) > 0:
            final.extend(right)
            right = []
        elif len(left) > 0:
            final.extend(left)
            left = []
    return final


arr = list(map(int,input().split(' ')))
print ("List before sorting:",arr)
final = mergesort(arr)
print ("After sorting:",final)

I have seen the second formula used in case of quicksort algo. The question is if my objective is to divide the array (as in the case of quicksort) why does it goes into an infinite loop.

I am very puzzled and can not come to any logical conclusion.

Can someone please throw some light into the matter? Thanks a lot in advance.

Solution

The second method should be used when working with a single array rather than multiple instances of a sub-array. Instead of using actual separate sub-arrays, the original array is split into logical sub-arrays via an index range. The mergesort function would take 3 parameters, mergesort(arr, start, end), and the caller would call mergesort(arr, 0, len(arr)). The merge function would take 4 parameters, merge(arr, start, mid, end).

Efficiency could be improved using an entry function that takes one parameter, mergesort(arr). It would allocate a single working array tmp and pass that to the internal functions, the call from mergesort(arr) would be mergesort(arr, tmp, 0, len(arr)). The mergesort function would be mergesort(arr, tmp, start, end). The merge function would be merge(arr, tmp, start, mid, end).

Answered By - rcgldr