pythonmergesortclrs

Mergesort resulting in error in CLRS (3rd edition)


According to CLRS(3rd edition) ch2 pages 31-34, here's the pseudocode and respective code for merge and merge_sort.

merge

def merge(a, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    left, right = [], []
    for i in range(1, n1):
        left.append(a[p + i - 1])
    for j in range(1, n2):
        right.append(a[q + j])
    left.append(float('inf'))
    right.append(float('inf'))
    i, j = 1, 1
    for k in range(p, r):
        if left[i] <= right[j]:
            a[k] = left[i]
            i += 1
        else:
            a[k] = right[j]
            j += 1

merge-sort

def merge_sort(a, p, r):
    if p < r:
        q = (p + r) // 2
        merge_sort(a, p, q)
        merge_sort(a, q + 1, r)
        merge(a, p, q, r)

And here's how it should be used:

how

if __name__ == '__main__':
    size = 100
    s = [random.randint(0, size) for _ in range(size)]
    print(s)
    merge_sort(s, 1, size)

results in:

[28, 4, 63, 29, 86, 36, 58, 87, 89, 23, 99, 38, 13, 22, 87, 77, 51, 62, 27, 35, 81, 23, 96, 92, 46, 21, 24, 44, 35, 54, 93, 61, 87, 1, 99, 44, 53, 77, 49, 52, 71, 12, 79, 60, 53, 74, 84, 92, 97, 8, 77, 92, 72, 33, 38, 61, 84, 13, 21, 62, 70, 88, 42, 59, 72, 48, 26, 12, 96, 78, 61, 99, 49, 38, 6, 37, 84, 17, 6, 39, 19, 15, 96, 71, 6, 92, 10, 61, 1, 83, 24, 57, 69, 78, 40, 6, 78, 84, 79, 14]
Traceback (most recent call last):
  File "algorithms/ch2/merge_sort.py", line 36, in <module>
    merge_sort(s, 1, size)
  File "algorithms/ch2/merge_sort.py", line 27, in merge_sort
    merge_sort(a, p, q)
  File "algorithms/ch2/merge_sort.py", line 27, in merge_sort
    merge_sort(a, p, q)
  File "algorithms/ch2/merge_sort.py", line 27, in merge_sort
    merge_sort(a, p, q)
  [Previous line repeated 3 more times]
  File "algorithms/ch2/merge_sort.py", line 29, in merge_sort
    merge(a, p, q, r)
  File "algorithms/ch2/merge_sort.py", line 16, in merge
    if left[i] <= right[j]:
IndexError: list index out of range

Is there something wrong with the code? Anything I am missing?


Solution

  • There are multiple problem in the transposition from the pseudo code to python code:

    Algorithms are better formalized with 0 based loops with an excluded upper bound. The pseudo-code is confusing and the book is not practical for programmers. You should consider books that analyzes algorithms with a practical approach in the language of your choice.

    Here is a modified version:

    # merge 2 adjacent slices from array a:
    # a[p:q] and a[q:r]
    def merge(a, p, q, r):
        n1 = q - p
        n2 = r - q
        left = a[p : q]
        right = a[q : r]
        i, j = 0, 0
        for k in range(p, r):
            if j >= n2 or (i < n1 and left[i] <= right[j]):
                a[k] = left[i]
                i += 1
            else:
                a[k] = right[j]
                j += 1
    
    def merge_sort(a, p, r):
        if r - p > 1:
            q = (p + r) // 2
            merge_sort(a, p, q)
            merge_sort(a, q, r)
            merge(a, p, q, r)
    
    if __name__ == '__main__':
        size = 100
        s = [random.randint(0, size) for _ in range(size)]
        print(s)
        merge_sort(s, 0, size)
        print(s)