66

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?

3
  • Why the need to only sort in-place? Feb 16, 2010 at 12:34
  • 3
    I think that this would be a good thing to request to be added to Python. It would just be optional arguments of start and end to the standard sort() method. Apr 27, 2010 at 18:48
  • 1
    A good reason for in-place sort is a case where you want to sort the end of the list (that is already mostly sorted, perhaps by a less-expensive key function), and then pop the last value. Ran into this use case when constructing a mostly-greedy TSP solution. Will likely go with the solution by @fviktor.
    – Jostikas
    Nov 22, 2016 at 20:30

3 Answers 3

88

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.

4
  • The OP actually asked for integers. For an array of integer, copying references is not supposed to be significantly faster than copying the actual values.
    – log0
    Jul 8, 2011 at 13:29
  • 2
    The question does not state that the list can only contain integers. The C++ example indeed operates on integers, but that does not mean that the question is limited only to that.
    – fviktor
    Sep 10, 2011 at 0:11
  • I don't think this is as good as using quicksort, because it requires O(N) extra memory, whereas quicksort uses O(1) extra memory. I left an answer down below with a quicksort implementation
    – Goodword
    Aug 24, 2021 at 18:25
  • It's not an in-place sort.
    – Jonathan
    Oct 30, 2022 at 21:48
41

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])
1
  • 4
    We do not want to use numpy
    – GilbertS
    Feb 23, 2020 at 15:50
2

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.