2018-05-27

有错误，，算法导论，无哨兵 情况

```

import sys

class mergesort():

    def merge_sort(self, A, p, r):

        if p < r:

            q = (p + r) / 2

            self.merge_sort(A, p, q)

            self.merge_sort(A, q+1, r)

            self.merge(A, p, q, r)

            return A

    def merge(self, A, p, q, r):

        n1 = q - p + 1

        n2 = r - q

        L = [0 for i in range(n1+1)]

        R = [0 for i in range(n2+1)]

        for i in range(n1):

            L[i] = A[p+i]

        for j in range(n2):

            R[j] = A[q+j+1]

        L[n1] = sys.maxint

        R[n2] = sys.maxint

        i = 0; j = 0

        for k in range(p, r):

            if (i!=n1 and j!=n2):

                if L[i] <= R[j]:

                    A[k] = L[i]

                    i += 1

                else:

                    A[k] = R[j]

                    j += 1               

            else:

                onlyonetime1=1

                onlyonetime2=1

                if ( i==n1 and onlyonetime1) :

                    #A[k] = R[j]

                    #j += 1 

                    kaka=0

                    for nn in range(j,n2):

                        A[k+kaka]=R[nn]

                        kaka+=1

                    onlyonetime1=0 

                if (j==n2 and onlyonetime2):

                    #j==n2

                    #A[k] = R[j]

                    #j += 1 

                    baba=0

                    for mm in range(i,n1):

                        A[k+baba]=L[mm]

                        baba+=1

                    onlyonetime2=0

sort = mergesort()

A = [1,3,5,7,9,11,20,40,60,80,100,120]

print sort.merge_sort(A, 0, len(A)-1)

```

123123

```

$python main.py

Traceback (most recent call last):  File "main.py", line 67, in     print sort.merge_sort(A, 0, len(A)-1)  File "main.py", line 9, in merge_sort    self.merge_sort(A, q+1, r)  File "main.py", line 10, in merge_sort    self.merge(A, p, q, r)  File "main.py", line 50, in merge    A[k+kaka]=R[nn]IndexError: list assignment index out of range

```

原因未找到，先记录下来