MergeSort - Strange Verhalten bei numpy Verwendung zu generieren Testsequenz

Question

Es folgt eine schnelle Umsetzung von MergeSort ich in Python eckt:

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] ! 

Diese Implementierung aus unerklärlichen Gründen versagt, wenn ich numpy verwenden für mich zufällig Arrays zu erzeugen, während bei Ich hardcodiere genau eine der fehlerhaften numpy generierten Sequenzen und führe den Code aus, er sortiert sich perfekt. Gibt es etwas, das ich vermisse?

Answer 1

Numpy-Arrays verhalten sich nicht wie Listen. Der Zusammenführungsschritt schlägt fehl, da x und y Ansichten von a sein würden, wenn a ein numpy Array ist. Sie können list(a) zum mergeSort Routine übergeben, damit es funktioniert:

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] !