Q:

MergeSort - Strange Behaviour when using numpy to generate test sequence

Following is a quick implementation of MergeSort I cooked up in python:
import numpy 
def mergeSort(a):
    if len(a) ==1:  
        return
    if len(a) == 2:
        if a[0] > a[1]:
            tmp = a[0]
            a[0] = a[1]
            a[1] = tmp
        return
    x = a[0:len(a)/2]
    y = a[len(a)/2:]
    mergeSort(x)
    mergeSort(y)
    j=0
    k=0
    for i in xrange(len(a)):
        if j == len(x) or k<len(y) and x[j] > y[k]:
            a[i] = y[k]
            k = k + 1
        else:
            a[i] = x[j]
            j = j + 1

a = numpy.random.randint(100, size=3) # Generates say [20  3 75]
mergeSort(a) 
print a # Yields [3, 3, 75] !
a = [20,3,75] 
mergeSort(a) 
print a # Yields [3, 20, 75] !

This implementation inexplicably fails when I use numpy to generate random arrays for me whereas if I hardcode exactly one of the failing numpy generated sequence and run the code, it sorts perfectly. Is there anything I'm missing?

A:

Numpy arrays don't behave the same as lists. The merge step fails because x and y would be views of a when a is a numpy array. You can pass list(a) to the mergeSort routine to make it work:   
import numpy 
def mergeSort(a):
    if len(a) ==1:  
        return
    if len(a) == 2:
        if a[0] > a[1]:
            tmp = a[0]
            a[0] = a[1]
            a[1] = tmp
        return
    x = a[0:len(a)/2]
    y = a[len(a)/2:]
    mergeSort(x)
    mergeSort(y)
    j=0
    k=0
    for i in xrange(len(a)):
        if j == len(x) or k<len(y) and x[j] > y[k]:
            a[i] = y[k]
            k = k + 1
        else:
            a[i] = x[j]
            j = j + 1

a = numpy.random.randint(100, size=3) # Generates say [20  3 75]
a = list(a)
mergeSort(a)
a = numpy.array(a)
print a # correctly Yields [3, 20, 75] !
a = [20,3,75] 
mergeSort(a) 
print a # Yields [3, 20, 75] !

