python排序算法问题

Question

你能解释一下这段代码的逻辑吗？这是排序算法。我不太明白逻辑。我不知道返回后的延续是如何工作的

def merge_sort(unsorted_list):
   if len(unsorted_list) <= 1:
      return unsorted_list
# Find the middle point and devide it
   middle = len(unsorted_list) // 2
   left_list = unsorted_list[:middle]
   right_list = unsorted_list[middle:]

   left_list = merge_sort(left_list)
   right_list = merge_sort(right_list)
   return list(merge(left_list, right_list))

# Merge the sorted halves
def merge(left_half,right_half):
   res = []
   while len(left_half) != 0 and len(right_half) != 0:
      if left_half[0] < right_half[0]:
         res.append(left_half[0])
         left_half.remove(left_half[0])
      else:
         res.append(right_half[0])
         right_half.remove(right_half[0])
   if len(left_half) == 0:
      res = res + right_half
   else:
      res = res + left_half
   return res
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(unsorted_list)

Answer 1

我试图跟踪上面的代码，发现这个排序算法逻辑工作不正确。

Explanation :

unsorted_list = [64, 34, 25, 12, 22, 11, 90]
middle = 3
left_half = [64,34,25]
right_half = [12,22,11,90]
res = []// new list to append all the elements after sorting

The above logic compares left_half and right_half elements :
The comparison happens until both lists is empty!

left_half[0] = 64 , right_half[0]=12  => 64<12 (false) => appends right_half[0] to res then removes the right_half[0] from right_half list so that we will not compare it again [which is actually false logic]

left_half[0]=64 , right_half[0]=22 => 64<22 (false) => appends right_half[0] 
to res then removes 22 from right_half list, now res =[12,22]

left_half[0]=64 , right_half[0]=11 => 64<11 (false) => appends right_half[0] 
to res then removes 11 from right_half list, now res =[12,22,11]

left_half[0]=64 , right_half[0]=90 => 64<90 (true) => appends left_half[0] 
to res then removes 64 from left_half list, now res =[12,22,11,64]

left_half[0]=34 , right_half[0]=90 => 34<90 (true) => appends left_half[0] 
to res then removes 34 from left_half list, now res =[12,22,11,64,34]

left_half[0]=25 , right_half[0]=90 => 25<90 (true) => appends left_half[0] 
to res then removes 25 from left_half list, now res =[12,22,11,64,34,25]

now, it goes to if condition where left_half list is empty (because of which it quits the while loop) and right_half has one element, so it directly appends that item to res list

so res = [12,22,11,64,34,25,90] // which is the wrong output