I guess you tested with Python lists when you found the code working very well. Now you a using it with a NumPy array. The crucial difference is that slicing a NumPy array as in here
lefthalf = alist[:mid]
righthalf = alist[mid:]
creates views over the original array, while slicing a list creates copies.
When your algorithm overwrites alist
by merging lefthalf
and righthalf
, all three lists must be separate; otherwise it may overwrite items lefthalf
that have not yet been merged.
The bug can be triggered by a small array:
>>> l = np.arange(10,0,-1)
>>> l
array([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
>>> mergeSort(l)
>>> l
array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1])