algorithm - In-place QuickSort in Python -

i had implement quicksort algorithm homework in language of choice , chose python.

during lectures, we've been told quicksort memory efficient because works in-place; i.e., has no additional copies of parts of input array recursions.

with in mind, tried implement quicksort algorithm in python, shortly afterwards realized in order write elegant piece of code have pass parts of array function while recursing. since python creates new lists each time this, have tried using python3 (because supports nonlocal keyword). following commented code.

def quicksort2(array): # create local copy of array. arr = array      def sort(start, end):         # base case condition         if not start < end:             return          # make known inner function work on arr         # outer definition         nonlocal arr          = start + 1         j = start + 1          # choosing pivot first element of working part         # part of arr         pivot = arr[start]          # start partitioning         while j <= end:             if arr[j] < pivot:                 temp = arr[i]                 arr[i] = arr[j]                 arr[j] = temp                 += 1             j += 1         temp = arr[start]         arr[start] = arr[i - 1]         arr[i - 1] = temp         # end partitioning          # recurse on both partitions         sort(start + 0, - 2)         sort(i, end)     sort(0, len(array) - 1) 

now, i'm not sure whether did job or missing something. have written more pythonic version of quicksort surely doesn't work in-place because keeps returning parts of input array , concatenates them.

my question is, way of doing in python? have searched both google , haven't found true in-place implementation of quicksort, thought it'd best ask.

sure not best way, plus famous algorithm have dozens of perfect implementations.. mine, quite easy understand

def sub_partition(array, start, end, idx_pivot):      'returns position pivot winds up'      if not (start <= idx_pivot <= end):         raise valueerror('idx pivot must between start , end')      array[start], array[idx_pivot] = array[idx_pivot], array[start]     pivot = array[start]     = start + 1     j = start + 1      while j <= end:         if array[j] <= pivot:             array[j], array[i] = array[i], array[j]             += 1         j += 1      array[start], array[i - 1] = array[i - 1], array[start]     return - 1  def quicksort(array, start=0, end=none):      if end none:         end = len(array) - 1      if end - start < 1:         return      idx_pivot = random.randint(start, end)     = sub_partition(array, start, end, idx_pivot)     #print array, i, idx_pivot     quicksort(array, start, - 1)     quicksort(array, + 1, end) 

ok first seperate function partition subroutine. takes array, start , end point of interest, , index of pivot. functions should clear

quicksort call partition subroutine first time on whole array; call recursevely sort pivot , after.

ask if dont understand something