How to find the worst case permutation for the MergeSort algorithm

Question

I am getting a recursion error and when reassigning the recursive limit, I get a memory error when trying to run the following code.

def join(A, left, right, l, m, r):
    x = 0
    for x in range(m-l):
        A[x] = left[x]
    for j in range(r-m):
        A[x+j] = right[j]enter code here

def split(A, left, right, l, m, r):
    for i in range(0, m-l, 1):
        left[i] = A[i*2]
    for i in range(0, r-m, 1):
        right[i] = A[i*2+1]

def generateWorstCase(A, l, r):
    if l < r:
        m = int(l + (r-1) / 2)
        left = [0 for i in range(m - l + 1)]
        right = [0 for i in range(r - m)]
        split(A, left, right, l, m, r)
        generateWorstCase(left, l, m)
        generateWorstCase(right, m+1, r)
        join(A, left, right, l, m, r)

arr = [1, 2, 3, 4, 5, 6, 7, 8]
generateWorstCase(arr, 0, len(arr)-1)
print(arr)

I tried translating the example given from geeksforgeeks https://www.geeksforgeeks.org/find-a-permutation-that-causes-worst-case-of-merge-sort/, and I am still confused about writing the code in python. I understand the fundamentals of how it works (as in it causes the mergeSort algorithm to compare the highest amount). I appreciate any tips to help with this.

Answer 1

The main problem is a typo here: m = int(l + (r-1) / 2).

Do not use l as an identifier because it looks confusingly similar to 1 in many fonts. The correct formula to compute the middle index is:

    m = l + (r-l) // 2

Note that using the integer division // instead of / avoids the need for the conversion int().

There is another bug in the join function: for x in range(m-l) will forget the last item in the slice because m is included rather than excluded. The ubiquitous convention in mergesort implementations to include the slice boundaries is confusing, causing off by one errors such as this one. Consider using r as the index of the first element after the slice.

There are more problems in the code, namely a confusion between temporary arrays and slices of the array A. It is simpler to reason with temporary arrays only.

Here is a simplified version:

def generateWorstCase(A):
    n = len(A)
    if n > 1:
        m = n // 2
        left = [A[i*2] for i in range(n-m)]
        right = [A[i*2+1] for i in range(m)]
        A = generateWorstCase(left) + generateWorstCase(right)
    return A

arr = [1, 2, 3, 4, 5, 6, 7, 8]
print(generateWorstCase(arr))

Output: [1, 5, 3, 7, 2, 6, 4, 8]

This code can be further simplified by taking advantage of Python's superior expressivity:

def generateWorstCase(A):
    return A if len(A) <= 1 else generateWorstCase(A[::2]) + generateWorstCase(A[1::2])

arr = [1, 2, 3, 4, 5, 6, 7, 8]
print(generateWorstCase(arr))