How to deal with scope in a recursive python sort function

Question

I am implementing Stooge Sort in Python and I can't understand why my changes to the ordering of my array is not sticking. In other words, it appears that as I drill down recursively the cells are being swapped, but then after the function returns the ordering of my array is unchanged. Is it a scope issue, or some other pythonism I don't understand yet? Or is my algorithm incorrect?

import math

def StoogeSort(A):

    n = len(A)

    if (n == 2 and A[0] > A[1]):

        tmp = A[0]
        A[0] = A[1]
        A[1] = tmp 

    elif n > 2:

        m = int(math.ceil((2 * n) / 3)) 
        StoogeSort(A[0:m]) 
        StoogeSort(A[m-n:n]) 
        StoogeSort(A[0:m]) 

    return A


A = [4,2,1]
StoogeSort(A)
print "End:",A
A = [44,12,8,33,100]
StoogeSort(A)
print "End:",A

List slices are copies of the list themselves. id(A) != id(A[0:m]) — Oluwafemi Sule, Apr 14 '19 at 21:39

score 1 · Answer 1 · answered Apr 14 '19 at 21:39

The problem lies in your slices - A[0:m], etc. These don't create a view into the original list, but rather create new lists.

You could use numpy arrays as described at the bottom of this answer, or use the return values of your recursive calls in order to construct a new list to be returned.

score 0 · Answer 2 · answered Apr 14 '19 at 22:15

1.- You are sending copies of your original array to recursion and not just parts of the original array. 2.- Although you will send parts of original array, pseudocode Stooge Sort algorithm doesn't work with parts of array, just indexes.

def StoogeSort(L, i, j):
    if L[i] > L[j]: #<-- always switching elements (not just for n=2)
        L[j],L[i]=L[i],L[j]  
    if (j - i + 1) > 2:
        t = int((j - i + 1) / 3)
        StoogeSort(L, i, j-t)  #<-- here, sending indexes.
        StoogeSort(L, i+t,j)
        StoogeSort(L, i, j-t)
    return L

>>> L = [7,8,9,5,6,4,2,1]
>>> StoogeSort(L, 0, len(L)-1)
[1, 2, 4, 5, 6, 7, 8, 9]

How to deal with scope in a recursive python sort function

2 Answers2