Два варианта sort в Python

В Python есть две функции сортировки, которые отличаются на один существенный момент:

arr = [3, 1, 4, 1, 5, 9, 2, 6]

# 1) list.sort() — in-place, модифицирует arr, возвращает None
arr.sort()
print(arr)           # [1, 1, 2, 3, 4, 5, 6, 9]

# 2) sorted() — out-of-place, возвращает новый список, arr не меняется
arr = [3, 1, 4, 1, 5, 9, 2, 6]
new_arr = sorted(arr)
print(arr)           # [3, 1, 4, 1, 5, 9, 2, 6] — не изменился
print(new_arr)       # [1, 1, 2, 3, 4, 5, 6, 9]

Оба используют один и тот же алгоритм — Timsort. Разница только в том, что одна модифицирует исходный массив, а другая возвращает новый.

Понятие in-place

• Strict in-place — O(1) extra memory.
• Loose in-place — O(log n) extra (например, стек рекурсии).

Sorting:

Strict in-place — лучше всего для embedded и для очень большого объёма данных. Loose in-place (quicksort) — компромисс: O(log n) extra обычно ничтожно.

Out-of-place (merge, Timsort) — приходится платить O(n) extra. Это критично для огромных массивов: 100 ГБ массив + 100 ГБ temp buffer = 200 ГБ требований к RAM.

Сколько памяти жрёт Timsort на самом деле

Хотя Timsort в worst case требует O(n) temp memory, на практике он работает с переиспользуемым буфером. Размер буфера определяется максимальным merge — и он редко достигает O(n).

Также есть стек runs, хранящий O(log n) границ.

В CPython реализация Timsort выделяет временную память кусками, что снижает peak usage. На массиве 10М int64 (80 МБ) Timsort может использовать ~40 МБ extra. Это не O(n) в smallest sense, но и не O(1).

list.sort vs sorted: когда что

list.sort():

• Модифицирует list in-place.
• Не возвращает результата (None).
• Не создаёт копию — меньше памяти.
• Работает только на list, не на tuple/iterable.

sorted():

• Возвращает новый list (исходный не меняется).
• Принимает любой iterable (list, tuple, generator, dict.keys, str, …).
• Создаёт копию исходных данных перед сортировкой.

# с list — sorted() копирует в новый list
arr_tuple = (3, 1, 4, 1, 5)
new_list = sorted(arr_tuple)        # tuple -> list
print(new_list)                     # [1, 1, 3, 4, 5]
print(type(new_list))               # <class 'list'>

# не работает на tuple.sort()
# arr_tuple.sort()   # AttributeError

Когда выбирать:

Зачем «in-place» вообще

Главная причина — память. Случай: огромный массив, например 10 ГБ float’ов в numpy. Сортировка через Timsort потребует ~10 ГБ временного буфера. Если у вас 16 ГБ RAM, вы рискуете уйти в swap.

Решение — in-place quicksort или heap sort:

import numpy as np
arr = np.array([...], dtype=np.float64)
arr.sort(kind='quicksort')   # in-place, in-place introsort

Numpy arr.sort() (метод) — in-place. np.sort(arr) — копия. Это полностью аналогично Python list.sort/sorted.

In-place sort через permutation

Часто хочется отсортировать массив по ключу, лежащему в другом массиве. Например, DataFrame: отсортировать строки по колонке ts, при этом не двигать сами 20 колонок данных.

Pattern: argsort + take.

import numpy as np

ts = np.array([5, 1, 4, 2, 3])
data = np.array(["a", "b", "c", "d", "e"])

perm = np.argsort(ts)        # [1, 3, 4, 2, 0] — индексы в порядке возрастания ts
sorted_ts = ts[perm]         # [1, 2, 3, 4, 5]
sorted_data = data[perm]     # ["b", "d", "e", "c", "a"]

Это не in-place в смысле original arrays (создаются новые), но избегает повторного копирования всех колонок при каждом swap — то, что делает прямая sort с компаунд-ключом.

Pandas использует именно permutation подход:

df.sort_values('ts')   # внутри: np.argsort на ts, потом fancy indexing на всех колонках

Это O(n) extra на permutation array, плюс по O(n) на колонку для применения. Total O(n) extra, не O(n*k).

DE-кейс: сортировка in-place при ограниченной RAM

Сценарий: у вас 8 ГБ RAM, нужно отсортировать 5 ГБ массив int64.

Если sorted(big_array) — будет ещё 5 ГБ под результат и ~3-5 ГБ под Timsort buffer = total 13-15 ГБ. Не помещается, swap.

Решение:

1. big_array.sort() (list.sort) — экономит 5 ГБ под результат, но Timsort всё равно использует buffer.
2. numpy arr.sort(kind='quicksort') — in-place quicksort, O(log n) extra. Помещается легко.
3. External sort — разбить на чанки, сортировать по очереди, merge.

DE-кейс: sort на read-only данных

Сценарий: вы работаете с массивом, который нельзя модифицировать — например, это разделяемая память между процессами или результат запроса, который ещё нужен.

arr.sort() нельзя — это бы разрушило исходник. Только sorted(arr) — out-of-place, возвращает новый.

В numpy для readonly-массивов:

arr.flags.writeable = False
np.sort(arr)         # OK — копирует
arr.sort()           # ValueError: assignment destination is read-only

Сложность памяти подробно

Special case: numpy in-place

Numpy предоставляет несколько kind параметров для np.sort и arr.sort():

arr.sort(kind='quicksort')   # introsort, in-place, не stable
arr.sort(kind='mergesort')   # Timsort-like, out-of-place, stable
arr.sort(kind='heapsort')    # heap sort, in-place, не stable
arr.sort(kind='stable')      # alias для mergesort

Default — quicksort (точнее introsort). Это in-place и быстрый. Если нужна stability — явно kind='stable'.

Numpy in-place sort на 100M int64 — порядка 5-7 секунд на современном x86, peak memory почти равна размеру массива (800 МБ). Mergesort на тех же данных — 8-10 секунд, peak memory ~1.6 ГБ.

Что выбрать по умолчанию

Для Python list:

• arr.sort() если list ваш и можно изменить;
• sorted(arr) если нужен новый список или iterable;
• помните, что оба — Timsort (stable).

Для numpy:

• arr.sort() (in-place, quicksort default) — для больших массивов;
• np.sort(arr, kind='stable') — если нужна stability;
• np.argsort + fancy indexing — для DataFrame-like permutation sort.

Для pandas:

• df.sort_values(by) — внутри numpy + permutation, эффективно.

Попробуй сам

import numpy as np
import time
import sys

N = 10**7
arr = np.random.randint(0, 10**9, size=N, dtype=np.int64)

# 1) in-place quicksort
arr1 = arr.copy()
t = time.perf_counter()
arr1.sort(kind='quicksort')
print(f"quicksort in-place: {time.perf_counter() - t:.3f} s")

# 2) out-of-place sort
arr2 = arr.copy()
t = time.perf_counter()
sorted_arr = np.sort(arr2, kind='stable')
print(f"sort out-of-place: {time.perf_counter() - t:.3f} s")

Ожидаемое:

• quicksort: ~0.4-0.6 с,
• stable: ~0.6-1.0 с.

Stable требует extra memory, но даёт стабильность. Quicksort быстрее и in-place, но не stable.

Plus measure peak memory с tracemalloc, чтобы увидеть фактическую разницу.

В следующем уроке — параллельная сортировка: как распределить работу на несколько ядер и почему merge sort легче параллелится, чем quicksort.