69

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?

Sнаđошƒаӽ
  • 16,753
  • 12
  • 73
  • 90
Headcrab
  • 6,838
  • 8
  • 40
  • 45
  • Why the need to only sort in-place? – Matthew Schinckel Feb 16 '10 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. – Justin Peel Apr 27 '10 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 '16 at 20:30

3 Answers3

91

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.

Roberto Bonvallet
  • 31,943
  • 5
  • 40
  • 57
fviktor
  • 2,861
  • 20
  • 24
  • 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 08 '11 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 '11 at 00: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 '21 at 18:25
  • It's not an in-place sort. – Jonathan Oct 30 '22 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])
jfs
  • 399,953
  • 195
  • 994
  • 1,670
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)
Goodword
  • 1,565
  • 19
  • 27