According to CLRS(3rd edition) ch2 pages 31-34, here's the pseudocode and respective code for merge
and merge_sort
.
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
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:
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?
There are multiple problem in the transposition from the pseudo code to python code:
in the pseudocode for i = 1 to n1, n1 is included, so you should use range(1, n1 + 1)
same remark for for k = p to r, use range(p, r + 1)
the algorithm uses infinite guard values (∞), a mathematical concept that does not fare well in code. If the list does contain infinite float values, the algorithm will fail. You should instead test index values in the merge loop and not rely on guard values.
list index values start at 0
in C and most programming languages, so the initial call mergesort(s, 1, size)
is inconsistent unless you subtract 1
from all index values in subscripting expressions.
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)