Алгоритм  в котором сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения. [Сложность алгоритма](Оценка%20сложности%20алгоритма): $O(n)$.
#### Алгоритм
Если входные элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является линейным. Это возможно благодаря определенным предположениям о входных данных. При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке \[0, 1).

Идея алгоритма заключается в том, чтобы разбить отрезок \[0, 1) на $n$ одинаковых отрезков (карманов), и разделить по этим карманам $n$ входных величин. Поскольку входные числа равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах. Отсортированный массив получается путём последовательного перечисления элементов каждого кармана.
#### Пример
![[sort_bucket.png]]
#### В виде кода
```python
def block_sort(arr, block_size=5):
    if not arr:
        return arr
    min_val = min(arr)
    max_val = max(arr)
    block_count = (max_val - min_val) // block_size + 1
    blocks = [[] for _ in range(block_count)]
    for x in arr:
        index = (x - min_val) // block_size
        blocks[index].append(x)
    result = []
    for block in blocks:
        block.sort()
        result.extend(block)
    return result
```