Sort a part of a list in place

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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)