Параллельное слияние и сортировка выборкой

Если ты знаешь, как слить два массива через ранги, как при этом не перепутать равные элементы и зачем в сортировке выборкой брать образцов с запасом, листай до «Теперь сам».

Как думаешь, где окажется элемент

Два отсортированных массива: A = 1, 4, 4, 9 и B = 2, 4, 6. В слитом массиве из семи элементов - на каком месте будет 9 из A? А 6 из B? Отвечай, не сливая массивы целиком.

Ответь себе до чтения. 9 - последний в A (номер 3), и в B все три элемента меньше: место 3 + 3 = 6. 6 - номер 2 в B, в A меньше его три элемента: место 2 + 3 = 5. Ни один из ответов не потребовал знать, где окажутся остальные. С равными элементами чуть сложнее - о них ниже.

На что это похоже

Две колонны школьников, каждая уже построена по росту, и их надо слить в одну. Учитель не переставляет детей по одному. Он просит каждого посмотреть на другую колонну и посчитать, сколько там ребят ниже него. Твоё место в общей колонне - твоё место в своей плюс это число. Все считают одновременно, и через минуту колонна построена.

Если двое одного роста из разных колонн, договорённость нужна заранее: например, дети из первой колонны встают раньше. Иначе оба займут одно место.

Механизм: ранг в чужом массиве

Элемент A[i] встаёт на место i + ранг_B(A[i]), где ранг - число элементов B, строго меньших A[i]. Элемент B[j] встаёт на j + ранг_A(B[j]), но здесь считаются элементы A, меньшие или равные B[j]. Несимметричность и решает спор равных: при равенстве элементы из A идут раньше, места не совпадают, и слияние устойчиво.

Каждый ранг - двоичный поиск, ⌈log₂(n + 1)⌉ сравнений. Все n + m поисков независимы: глубина O(log n), работа O(n log n) - против O(n) у обычного слияния. Работоэффективная версия делит массивы на p кусков: двоичным поиском ищут только границы кусков (так, чтобы каждый процессор получил ⌊n / p⌋ или ⌈n / p⌉ элементов ответа: для границы с номером r двоичным поиском находят, сколько из первых r элементов ответа придут из A, остальные - из B), а дальше каждый сливает свой кусок обычным циклом. Так устроены параллельные слияния в библиотеках.

Сортировка выборкой (sample sort) для p процессоров: взять из массива s · p случайных образцов, отсортировать их и взять образцы с номерами s, 2s, …, (p − 1)s как границы - получится p − 1 граница. Каждый элемент двоичным поиском находит свою корзину, корзины сортируются независимо и склеиваются. Множитель s - запас выборки (oversampling): чем он больше, тем ровнее корзины, как правило: выборка случайная, и гарантий для отдельного запуска нет.

Правило

Позиция элемента в слиянии - его номер в своём массиве плюс ранг в чужом. Для элементов первого массива ранг - число строго меньших, для второго - число меньших или равных; так равные не сталкиваются и слияние устойчиво. Слияние рангами: глубина O(log n), работа O(n log n); сортировка слиянием с ним - глубина O(log² n). При малом p работоэффективнее сортировка выборкой: p − 1 граница из s · p случайных образцов, корзины сортируются независимо.

Разбор: слияние рангами и цена сортировки

Две функции двоичного поиска различаются одним знаком: < против <=. Программа сливает массивы из вопроса, помечая, откуда пришёл каждый элемент, а потом считает работу и глубину двух сортировок слиянием.

import math

def menshe(a, x):
    # сколько элементов отсортированного a строго меньше x
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def ne_bolshe(a, x):
    # сколько элементов a меньше или равны x
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def sliyanie_rangami(a, b):
    # каждый элемент сам находит своё место: свой номер плюс ранг в чужом
    c = [None] * (len(a) + len(b))
    for i in range(len(a)):
        c[i + menshe(b, a[i])] = ["A", a[i]]
    for j in range(len(b)):
        c[j + ne_bolshe(a, b[j])] = ["B", b[j]]
    return c

print(sliyanie_rangami([1, 4, 4, 9], [2, 4, 6]))
print("n | обычное: работа глубина параллелизм | рангами: то же")
for n in [1024, 65536]:
    lg = round(math.log2(n))
    # глубина: D(n) = D(n/2) + n  против  D(n) = D(n/2) + log n
    d1 = 2 * n - 2
    d2 = lg * (lg + 1) // 2
    w1 = n * lg
    w2 = n * lg * (lg + 1) // 2
    print(n, w1, d1, round(w1 / d1, 1), w2, d2, round(w2 / d2))

[['A', 1], ['B', 2], ['A', 4], ['A', 4], ['B', 4], ['B', 6], ['A', 9]]
n | обычное: работа глубина параллелизм | рангами: то же
1024 10240 2046 5.0 56320 55 1024
65536 1048576 131070 8.0 8912896 136 65536

Слияние верное, и обе четвёрки из A стоят раньше четвёрки из B. Таблица: работа, глубина и параллелизм двух сортировок. С последовательным слиянием параллелизм на 65 536 элементах - 8. Со слиянием рангами - 65 536, глубина 136 вместо 131 070. Но работа выросла в 8,5 раза: на уровне с кусками размера k каждый элемент делает двоичный поиск за log k, и вместо n log n получается порядка n log² n / 2. На восьми ядрах это медленнее последовательной сортировки - та самая лишняя работа из прошлой главы. Поэтому в библиотеках слияние режут на p кусков, а не на n поисков.

Разбор: сколько образцов брать

Сортировка выборкой хороша, если корзины примерно равны: время - это самая большая корзина. Возьмём 4000 случайных чисел, восемь корзин, и посмотрим, насколько самая большая корзина больше идеальных 500 при разном запасе выборки.

import random

def razbit_vyborkoj(x, p, s):
    # s * p случайных образцов; границы - образцы номер s, 2s, ...
    obrazcy = []
    for k in range(s * p):
        obrazcy.append(x[random.randint(0, len(x) - 1)])
    obrazcy.sort()
    granicy = []
    for k in range(1, p):
        granicy.append(obrazcy[k * s])
    korziny = [0] * p
    for v in x:
        k = 0
        while k < p - 1 and v >= granicy[k]:
            k = k + 1
        korziny[k] = korziny[k] + 1
    return korziny

random.seed(8)
x = []
for i in range(4000):
    x.append(random.randint(0, 10 ** 6))
p = 8
print("ровно было бы", len(x) // p)
for s in [1, 4, 16, 64]:
    k = razbit_vyborkoj(x, p, s)
    print(s, k, round(max(k) / (len(x) / p), 2))

ровно было бы 500
1 [630, 1825, 184, 14, 404, 16, 26, 901] 3.65
4 [861, 832, 777, 318, 129, 376, 370, 337] 1.72
16 [569, 724, 546, 462, 514, 324, 458, 403] 1.45
64 [555, 428, 451, 566, 512, 516, 495, 477] 1.13

Без запаса (по одному образцу на корзину) самая большая корзина в 3,65 раза больше нужной: восемь случайных чисел плохо делят тысячи. С запасом 64 перекос 1,13. Цена запаса - сортировка s · p образцов, при s = 64 это 512 чисел против 4000: заметно, но окупается. В программе корзина ищется перебором границ, чтобы не повторять двоичный поиск ещё раз; в настоящей сортировке это двоичный поиск по p − 1 границе.

Что ломается без этого

Одинаковое правило для равных. Если обе стороны считают «строго меньше», равные 4 из A и B попадут в одну ячейку, и одна запись затрёт другую. Если обе считают «меньше или равно», ячейка между ними останется пустой. Симптом - потерянный элемент и None в ответе.

Границы без запаса. Сортировка выборкой по p − 1 случайному элементу: одна корзина получает треть массива, и один процессор работает втрое дольше остальных. На данных с повторами хуже: если все границы равны одному частому значению, весь хвост уходит в одну корзину - для этого корзину равных выделяют отдельно.

Слияние рангами на восьми ядрах. Логарифмическая глубина не окупает n log n работы на каждом уровне.

Зачем это в работе

Параллельная сортировка __gnu_parallel::sort в GCC режет массив на куски по числу потоков, сортирует их и сливает многопутевым слиянием с поиском границ - ровно та работоэффективная схема, что выше. Сортировка выборкой - основа распределённых сортировок: Spark при sortBy строит границы секций по выборке (RangePartitioner) именно затем, чтобы секции вышли ровными. DuckDB в версии 1.4 (сентябрь 2025) переписал сортировку в двухфазное слияние, которое использует все ядра в обеих фазах и при нехватке памяти уходит на диск - к этому вернёмся в главе о внешней памяти.

Теперь сам

1. A = 2, 5, 5, B = 1, 5, 8. На какие места встанут элементы B при слиянии рангами?
2. Сколько сравнений делает слияние рангами двух массивов по 1024 элемента, если двоичный поиск в массиве из 1024 элементов стоит 11 сравнений?
3. Почему в сортировке выборкой границы берут из отсортированной выборки через s, а не просто p − 1 случайный элемент?