Trying to implement an function that splits an array in half recursively, and here is my code

def mergeSort(array1, left, right):

   if left < right:

        mid = (left   right) // 2

        firstHalf = array1[left : mid]

        secondHalf = array1[mid : right]   []

        print("firstHalf is : ")
        print(firstHalf)

        print("secondHalf is")
        print(secondHalf)

        mergeSort(firstHalf, left, mid)

        mergeSort(secondHalf, mid 1, right)


nums1 = [11, 25, 13, 44, 57, 69, 17, 8, 19, 120]

low = 0

high = len(nums1)

mergeSort(nums1, low, high)

To my surprise, when I run the program in terminal, I only see the division from the left side getting printed out.

firstHalf is : 
[11, 25, 13, 44, 57]
secondHalf is
[69, 17, 8, 19, 120]
firstHalf is : 
[11, 25]
secondHalf is
[13, 44, 57]
firstHalf is : 
[11]
secondHalf is
[25]
firstHalf is : 
[]
secondHalf is
[11]

I don't really know why. Where is the right half?

CodePudding user response：

This happens because you use offsets in the original list (left right mid) to slice in a much shorter list (firstHalf, secondHalf) that is already a slice from the original list. So these offsets are not correct and eventually point beyond the size of the much smaller secondHalf list.

Just think about it: the first time, secondHalf will be half the size of the original list, yet you make the second recursive call with offsets that start at mid 1, which is beyond that size.

To correct this, either always work with the full list as first argument to your function, or remove the other arguments (left, right). The second approach leads to this code:

def mergeSort(array1):
   if len(array1) > 1:
        mid = len(array1) // 2
        firstHalf = array1[:mid]
        secondHalf = array1[mid:]
        print("firstHalf is : ")
        print(firstHalf)
        print("secondHalf is")
        print(secondHalf)
        mergeSort(firstHalf)
        mergeSort(secondHalf)


nums1 = [11, 25, 13, 44, 57, 69, 17, 8, 19, 120]
mergeSort(nums1)

CodePudding user response：

The indexes left, mid, and right are positions in the original list. When you split it up, you can't use the same indexes in the recursion.

There are two ways you can implement this:

1. Don't pass indexes. Slice the list and call the function recursively with each slice, until the slice is less than 2 elements long.
2. Pass the entire list in each recursive call, along with updated low/high indexes each time.