MergeSort out-of-bound array access

[zzzDavid]

Hi,

I would like to report a possible bug on the merge sort kernel implementation that may cause out-of-bound array access: https://github.com/breagen/MachSuite/blob/6236e593012cb86b0d2f08d9fb9ba0411ff989b4/sort/merge/sort.c#L35-L36

The stop variable is set to SIZE, which is the same size as the array being sorted. However, on line 12 here: https://github.com/breagen/MachSuite/blob/6236e593012cb86b0d2f08d9fb9ba0411ff989b4/sort/merge/sort.c#L11-L13

The loop upper bound is inclusive. When stop is set to SIZE, there will be an out-of-bound array access a[SIZE] which causes segfault.

I believe changing stop to SIZE-1 should fix it. Here's a Python implementation verified against Python's own sort function:

N = 5

def merge(a, start, m, stop):
    temp = np.zeros(N, dtype=np.int32)
    for i in range(start, m + 1):
        temp[i] = a[i]
    for j in range(m+1, stop + 1):
        temp[m + 1 + stop - j] = a[j]

    i = start
    j = stop
    for k in range(start, stop + 1):
        tmp_j = temp[j]
        tmp_i = temp[i]
        if (tmp_j < tmp_i):
            a[k] = tmp_j
            j -= 1
        else:
            a[k] = tmp_i
            i += 1

def mergesort_reference(a):
    start = 0
    stop = N - 1
    m = 1
    while m < stop-start + 1:
        for i in range(start, stop, m+m):
            f = i
            mid = i + m - 1
            to = i + m + m - 1
            if to < stop:
                merge(a, f, mid, to)
            else:
                merge(a, f, mid, stop)
        m += m
    return a