Numpy Array Mergesort

Question

I'm new to Numpy and am trying to use an example merge sort program I found at: http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html

However, when I try using it on a numpy array by doing:

blist = np.array([54, 26, 93, 17, 77, 31, 44, 55, 20])
mergeSort(blist)

It prints out

[17 17 17 17 20 20 20 20 20]

instead of the output thats expected which works with a normal python list. Does anybody know why the program seems to not work with a numpy array but does with its intended input?

Answer 1

As has already been said, there is no expectation for code written for lists to generalise to NumPy arrays as well.

If you want to sort a NumPy array, you can use sorted()

blist = np.array([54, 26, 93, 17, 77, 31, 44, 55, 20])
print(sorted(blist))

The problem is to do with the way the merging functions assigns the new values to the array. If you run this you can see the problem:

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)
        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:               
                alist[k]=lefthalf[i]
                i=i+1
            else:
                print(lefthalf,"lefthalf before the incorrect assignment")
                print(alist[k],righthalf[j])
                alist[k]=righthalf[j]
                print(lefthalf,"lefthalf after the incorrect assignment")               
                j=j+1
            k=k+1


        while i < len(lefthalf):
            alist[k]=lefthalf[i]         
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
print("Merging ",alist)

It seems that the lefthalf references the values in the alist array and so therefore the assignment of the alist value to that in the righthalf also changes the value of the lefthalf at the same time.

Running this codeblock makes it more obvious:

alist = np.array([54,26])
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
print(lefthalf,"lefthalf before the incorrect assignment")
alist[0]=righthalf[0]
print(lefthalf,"lefthalf after the incorrect assignment") 

The problem is discussed here. In fact, you can actually fix it by adding .copy() after lefthalf = alist[:mid] righthalf = alist[mid:] i.e. lefthalf = alist[:mid].copy() etc.

Answer 2

The problem intrigues me, but I'm not sure that it is a good way to learn numpy. An iterative process like this does not make good use of array's unique qualities. It is just treating it like a list, and it is evident the fit isn't quite right.

---

Here's a run for a small list:

In [608]: alist=[3,2];arr=np.array(alist)
In [609]: mergeSort(alist)
Splitting  [3, 2]
Splitting  [3]
Merging  [3]
Splitting  [2]
Merging  [2]
Merging  [2, 3]

In [610]: mergeSort(arr)
Splitting  [3 2]
Splitting  [3]
Merging  [3]
Splitting  [2]
Merging  [2]
Merging  [2 2]

The difference is in that last merging step.

---

I modified the code to add more diagnostic prints

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                print('1',i,j,alist)
                i=i+1
            else:
                alist[k]=righthalf[j]
                print('2',i,j,alist)
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            print('3',i,j,alist)
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            print('4',i,j,alist)
            j=j+1
            k=k+1
    print("Merging ",alist)

run:

In [623]: alist=[3,2];arr=np.array(alist)
In [624]: mergeSort(alist)
Splitting  [3, 2]
Splitting  [3]
Merging  [3]
Splitting  [2]
Merging  [2]
2 0 0 [2, 2]
3 0 1 [2, 3]
Merging  [2, 3]

In [625]: mergeSort(arr)
Splitting  [3 2]
Splitting  [3]
Merging  [3]
Splitting  [2]
Merging  [2]
2 0 0 [2 2]
3 0 1 [2 2]
Merging  [2 2]

So it is 'merging' at 1 and 4 for the list, and 2 and 3 for the array. Can we figure out why? I suspect a difference in the if tests.

---

Looks like the fix is:

    lefthalf = alist[:mid].copy()
    righthalf = alist[mid:].copy()

As @duhamp noted with the array, changes to lefthalf changes righthalf. With lists, lefthalf and righthalf are copies of alist. But indexing alist[:mid] returns a view, not a copy. That's an important difference between lists and arrays.

More importantly, when you run into problems with Python code, and numpy code in particular, it helps to add diagnostic prints at suspected problem points. You could use the debugger, or as we did, temporarily modify the code. Either way, the problem is usually in small detail that you over looked with writing the code.