Python List Assignment Not Having Any Effect

Question

I'm relatively new to Python.

I'm trying to implement merge sort in python. However, a test case like [1, 2, 6, 4, 5] came out to be [1, 1, 1, 1, 1] when "sorted." After a long time, I found the cause to be in the merge algorithm. The actual algorithm looked fine, except I don't know why a certain part isn't working.

def merge(arr, left, right, start_pos):
   i = 0
   j = 0
   k = start_pos

   while i < len(left) or j < len(right):
       if i >= len(left):
           arr[k] = right[j] # This assignment has no effect
           j += 1
           k += 1
       elif j >= len(right):
           arr[k] = left[i] # Same here
           i += 1
           k += 1
       else:
           if arr[i] < arr[j]:
               arr[k] = arr[i] # Here
               i += 1
               k += 1
           else:
               arr[k] = arr[j] # And here
               j += 1
               k += 1

First of all, the goal was to be given an array called arr, and array called left, an array called right, and an int called start_pos, the merge algorithm replaces the values in arr starting at start_pos with left and right merged. However, as you can see in the comments, for some reason the assigment isn't working. I couldn't seem to figure out why. It probably won't be that much help, but just in case here is the whole code:

def merge_sort(arr):
    merge_sort_helper(arr, 0, len(arr))

def merge_sort_helper(arr, left, right):
    if left >= right - 1:
        return

    mid = int((left + right) / 2)
    merge_sort_helper(arr, left, mid)
    merge_sort_helper(arr, mid, right)
    merge(arr, arr[left : mid], arr[mid : right], left)


def merge(arr, left, right, start_pos):
   i = 0
   j = 0
   k = start_pos

   while i < len(left) or j < len(right):
       if i >= len(left):
           arr[k] = right[j]
           j += 1
           k += 1
       elif j >= len(right):
           arr[k] = left[i]
           i += 1
           k += 1
       else:
           if arr[i] < arr[j]:
               arr[k] = arr[i]
               i += 1
               k += 1
           else:
               arr[k] = arr[j]
               j += 1
               k += 1

The list assignment statement is working as expected. The problem is with the value that you are assigning to that list. — Pratik Joshi
– Pratik Joshi, Commented May 27, 2020 at 3:30
Please reduce and enhance this into the expected MRE. Show where the intermediate results deviate from the ones you expect. In particular, put in some strategic print commands to show what is actually happening as you work through the sort. I can't see that the assignment isn't working, because you neglected to show us. — Prune
– Prune, Commented May 27, 2020 at 3:34
Most of all, what confuses my is how you expect the values you assign to a temporary, local variable to be transferred accurately back to the main list. I don't think you quite understand which parameters are transient, and which map to variables in the main program (which you neglected to provide or trace). — Prune
– Prune, Commented May 27, 2020 at 3:36

meiwenhua · Accepted Answer · 2020-05-27 05:54:38Z

1

The merge function intent to genrate new sorted list by left sorted list and right sorted list. The error occur on if arr[i] < arr[j]:. you don't want compare arr[i] and arr[j], the compared value should be left[i] and right[j], select the smaller one fill to arr.

Here is the modified code

def merge_sort(arr):
    merge_sort_helper(arr, 0, len(arr))

def merge_sort_helper(arr, left, right):
    if left >= right - 1:
        return

    mid = int((left + right) / 2)
    merge_sort_helper(arr, left, mid)
    merge_sort_helper(arr, mid, right)
    merge(arr, arr[left : mid], arr[mid : right], left)


def merge(arr, left, right, start_pos):
   i = 0
   j = 0
   k = start_pos

   while i < len(left) or j < len(right):
       if i >= len(left):
           arr[k] = right[j]
           j += 1
           k += 1
       elif j >= len(right):
           arr[k] = left[i]
           i += 1
           k += 1
       else:
           if left[i] < right[j]:
               arr[k] = left[i]
               i += 1
               k += 1
           else:
               arr[k] = right[j]
               j += 1
               k += 1

l = [8,1,3,5,7,6,4,2,9]
merge_sort(l)
print(l)

answered May 27, 2020 at 5:54

meiwenhua

864 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Higigig Over a year ago

Thanks, I didn't notice that typo.

SVIS · Accepted Answer · 2020-05-27 03:26:41Z

1

Your calling of merge function seems to be culprit, where you're passing in the same list arr 3 times.

You would want the merge function to return a new list that is the merged output of left and right. This would also help you see the recursion in merge_helper more clearly

answered May 27, 2020 at 3:26

SVIS

581 silver badge12 bronze badges

Collectives™ on Stack Overflow

Python List Assignment Not Having Any Effect

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related