python实现二归并排序时，为什么只是交换了and两边条件的位置，一个能出结果，一个就报错？

Question

def merge(s1,s2,s):
    i = j = 0
    while i+j<len(s):
        if j==len(s2) or (i<len(s1) and s1[i]<s2[j]):
            s[i+j] = s1[i]
            i += 1
        else:
            s[i+j] = s2[j]
            j += 1

def merge_sort(s):
    n = len(s)
    if n < 2:
        return
    mid = n // 2
    s1 = s[0:mid]
    s2 = s[mid:n]
    merge_sort(s1)
    merge_sort(s2)
    merge(s1,s2,s)


s = [24,17,40,28,13,14,22,32,40,21,48,4,47,8,37,18,88,56,79,35,0,66,156]
merge_sort(s)
print(s)

这个代码是能正常运行的，结果是：

[0, 4, 8, 13, 14, 17, 18, 21, 22, 24, 28, 32, 35, 37, 40, 40, 47, 48, 56, 66, 79, 88, 156]

但是我只是改变了if 语句中 and两边语句 的位置，结果就报错了

 if j==len(s2) or (s1[i]<s2[j] and i<len(s1)):

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-9-5ac2ee75fd0c> in <module>()
     22 
     23 s = [24,17,40,28,13,14,22,32,40,21,48,4,47,8,37,18,88,56,79,35,0,66,156]
---> 24 merge_sort(s)
     25 print(s)

<ipython-input-9-5ac2ee75fd0c> in merge_sort(s)
     16     s1 = s[0:mid]
     17     s2 = s[mid:n]
---> 18     merge_sort(s1)
     19     merge_sort(s2)
     20     merge(s1,s2,s)

<ipython-input-9-5ac2ee75fd0c> in merge_sort(s)
     16     s1 = s[0:mid]
     17     s2 = s[mid:n]
---> 18     merge_sort(s1)
     19     merge_sort(s2)
     20     merge(s1,s2,s)

<ipython-input-9-5ac2ee75fd0c> in merge_sort(s)
     18     merge_sort(s1)
     19     merge_sort(s2)
---> 20     merge(s1,s2,s)
     21 
     22 

<ipython-input-9-5ac2ee75fd0c> in merge(s1, s2, s)
      2     i = j = 0
      3     while i+j<len(s):
----> 4         if j==len(s2) or (s1[i]<s2[j] and i<len(s1)):
      5             s[i+j] = s1[i]
      6             i += 1

IndexError: list index out of range

Answer 1

越界后, and的短路特性使得第二个条件没被执行. 另外我觉得没必要写这么复杂的条件, 可以在最后把剩下的放进去, 代码比较对称, 逻辑比较清晰:

def merge(s1, s2, s):
    i = j = 0
    while i < len(s1) and j < len(s2):
        if s1[i] < s2[j]:
            s[i+j] = s1[i]
            i += 1
        elif s1[i] >= s2[j]:
            s[i+j] = s2[j]
            j += 1
    while i < len(s1):
        s[i+j] = s1[i]
        i += 1
    while j < len(s2):
        s[i+j] = s2[j]
        j += 1

或者直接舍弃指标i和j, 用列表的pop移动.