python - Is this the correct implementation of merge sort?

Question

def merge(arr1, arr2):
    returned = []
    while len(arr1) > 0 and len(arr2) > 0:
        if arr1[0] >= arr2[0]:
            returned.append(arr2[0])
            arr2.pop(0)
        else:
            returned.append(arr1[0])
            arr1.pop(0)
    if len(arr1) > 0:
        returned = returned + arr1
    if len(arr2) > 0:
        returned = returned + arr2
    return returned

Above is the merge function. Below is the merge sort function.

def merge_sort(nums):
    #print("Merge sorting following array:")
    #print(nums)
    if len(nums) == 1:
        return nums
    else:
        middle = int(len(nums)/2)
        first_half = nums[:middle]
        #print("First half is:")
        #print(first_half)
        second_half = nums[middle:]
        #print("Second half is:")
        #print(second_half)
        return merge(merge_sort(first_half), merge_sort(second_half))

It feels like something is off because I timed it using the time module, and it was about 4 times as fast as a bubble sort algorithm, on a list 10 numbers long. I think I may be overthinking the merge function, but cannot put my finger on what I am doing wrong.

Answer 1

Your implementation is mostly functional, but it has some shortcomings:

• it cannot handle an empty list: such an argument will cause an infinite recursion resulting in a stack overflow. You should test if the length is <= 1.
• the merge function modifies its arguments by popping the first element repeatedly. This is likely a very costly approach. It would be more efficient to use index variables to iterate in arr1 and arr2.
• it does not implement a stable sort as equal elements are taken first from arr2 then from arr1.

Here is an alternative you can time and compare:

def merge(arr1, arr2):
    result = []
    i = 0
    j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i = i + 1
        else:
            result.append(arr2[j])
            j = j + 1
    return result + arr1[i:] + arr2[j:]

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    else:
        middle = len(nums) >> 1
        first_half = nums[:middle]
        second_half = nums[middle:]
        return merge(merge_sort(first_half), merge_sort(second_half))