Problem implementing Merge Sort from pseudo code python

Question

Im trying to implement merge sort in Python based on the following pseudo code. I know there are many implementations out there, but I have not been able to find one that followis this pattern with a for loop at the end as opposed to while loop(s). Also, setting the last values in the subarrays to infinity is something I haven't seen in other implementation. NOTE: The following pseudo code has 1 based index i.e. index starts at 1. So I think my biggest issue is getting the indexing right. Right now its just not sorting properly and its really hard to follow with the debugger. My implementation is at the bottom.

Current Output:

Input:  [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Merge Sort:  [0, 0, 0, 3, 0, 5, 5, 5, 8, 0]

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

def merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q

    L = [0] * (n1 + 1)
    R = [0] * (n2 + 1)

    for i in range(0, n1):
        L[i] = A[p + i]

    for j in range(0, n2):
        R[j] = A[q + 1 + j]

    L[n1] = 10000000 #dont know how to do infinity for integers
    R[n2] = 10000000 #dont know how to do infinity for integers

    i = 0
    j = 0

    for k in range(p, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

    return A

Answer 1

In mathematics, we represent all real numbers which are greater than or equal to i and smaller than j by [i, j). Notice the use of [ and ) brackets here. I have used i and j in the same way in my code to represent the region that I am dealing with currently.

ThThe region [i, j) of an array covers all indexes (integer values) of this array which are greater or equal to i and smaller than j. i and j are 0-based indexes. Ignore the first_array and second_array the time being.

Please notice, that i and j define the region of the array that I am dealing with currently.

Examples to understand this better

If your region spans over the whole array, then i should be 0 and j should be the length of array [0, length).

The region [i, i + 1) has only index i in it.

The region [i, i + 2) has index i and i + 1 in it.

def mergeSort(first_array, second_array, i, j):
    if j > i + 1:
        mid = (i + j + 1) // 2
        mergeSort(second_array, first_array, i, mid)
        mergeSort(second_array, first_array, mid, j)
        merge(first_array, second_array, i, mid, j)

One can see that I have calculated middle point as mid = (i + j + 1) // 2 or one can also use mid = (i + j) // 2 both will work. I will divide the region of the array that I am currently dealing with into 2 smaller regions using this calculated mid value.
In line 4 of the code, MergeSort is called on the region [i, mid) and in line 5, MergeSort is called on the region [mid, j).

You can access the whole code here.

Answer 2

Here is a rewrite of the algorithm with “modern” conventions, which are the following:

• Indices are 0-based
• The end of a range is not part of that range; in other words, intervals are closed on the left and open on the right.

This is the resulting code:

INF = float('inf')

def merge_sort(A, p=0, r=None):
    if r is None:
        r = len(A)
    if r - p > 1:
        q = (p + r) // 2
        merge_sort(A, p, q)
        merge_sort(A, q, r)
        merge(A, p, q, r)

def merge(A, p, q, r):
    L = A[p:q]; L.append(INF)
    R = A[q:r]; R.append(INF)
    i = 0
    j = 0
    for k in range(p, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

A = [433, 17, 585, 699, 942, 483, 235, 736, 629, 609]
merge_sort(A)
print(A)
# → [17, 235, 433, 483, 585, 609, 629, 699, 736, 942]

Notes:

• Python has a handy syntax for copying a subrange.
• There is no int infinity in Python, but we can use the float one, because ints and floats can always be compared.
• There is one difference between this algorithm and the original one, but it is irrelevant. Since the “midpoint” q does not belong to the left range, L is shorter than R when the sum of their lengths is odd. In the original algorithm, q belongs to L, and so L is the longer of the two in this case. This does not change the correctness of the algorithm, since it simply swaps the roles of L and R. If for some reason you need not to have this difference, then you must calculate q like this:

        q = (p + r + 1) // 2

Answer 3

First of all you need to make sure if the interval represented by p and r is open or closed at its endpoints. The pseudocode (for loops include last index) establishes that the interval is closed at both endpoints: [p, r].

With last observation in mind you can note that for k in range(p, r): doesn't check last number so the correct line is for k in range(p, r + 1):.

You can represent "infinity" in you problem by using the maximum element of A in the range [p, r] plus one. That will make the job done.

You not need to return the array A because all changes are being done through its reference.

Also, q = (p + (r - 1)) // 2 isn't wrong (because p < r) but correct equation is q = (p + r) // 2 as the interval you want middle integer value of two numbers.