# Sort a part of a list in place

Posted on

### Question :

Sort a part of a list in place

Let’s say we have a list:

``````a = [4, 8, 1, 7, 3, 0, 5, 2, 6, 9]
``````

Now, a.sort() will sort the list in place. What if we want to sort only a part of the list, still in place? In C++ we could write:

``````int array = { 4, 8, 1, 7, 3, 0, 5, 2, 6, 9 };
int * ptr = array;
std::sort( ptr + 1, ptr + 4 );
``````

Is there a similar way in Python?

I’d write it this way:

``````a[i:j] = sorted(a[i:j])
``````

It is not in-place sort either, but fast enough for relatively small segments.

Please note, that Python copies only object references, so the speed penalty won’t be that huge compared to a real in-place sort as one would expect.

if `a` is a `numpy` array then to sort `[i, j)` range in-place, type:

``````a[i:j].sort()
``````

Example:

``````>>> import numpy as np
>>> a = np.array([4, 8, 1, 7, 3, 0, 5, 2, 6, 9])
>>> a[1:4].sort()
>>> a
array([4, 1, 7, 8, 3, 0, 5, 2, 6, 9])
``````

To sort between two indices in place, I would recommend using quicksort. the advantage of quicksort over `array[start:end] = sorted(arr[start:end])` is that quicksort does not require any extra memory, whereas assigning to a slice requires O(n) extra memory.

I don’t believe there is an implementation in the standard library, but it is easy to write yourself. Here is an implementation that I copied and pasted from https://www.geeksforgeeks.org/quicksort-using-random-pivoting/

``````import random

def quicksort(arr, start , stop):
if(start < stop):
pivotindex = partitionrand(arr, start, stop)
quicksort(arr , start , pivotindex - 1)
quicksort(arr, pivotindex + 1, stop)

def partitionrand(arr , start, stop):

randpivot = random.randrange(start, stop)

arr[start], arr[randpivot] = arr[randpivot], arr[start]
return partition(arr, start, stop)

def partition(arr,start,stop):
pivot = start # pivot
i = start + 1 # a variable to memorize where the
# partition in the array starts from.
for j in range(start + 1, stop + 1):
if arr[j] <= arr[pivot]:
arr[i] , arr[j] = arr[j] , arr[i]
i = i + 1
arr[pivot] , arr[i - 1] = arr[i - 1] , arr[pivot]
pivot = i - 1
return (pivot)
``````

To sort between, say, indices 2 and 6 in your example (inclusive range), I would do something like this:

``````array = [4, 8, 1, 7, 3, 0, 5, 2, 6, 9]
quicksort(array, 2, 6)
print(array)
``````