Суть: нужно разбить элементы массива входных данных на k блоков. Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки.

[https://neerc.ifmo.ru/wiki/index.php?title=Карманная_Сортировка](https://lh7-us.googleusercontent.com/I_Yaz8L6JqxxWOyEsAYikyQ4_EKID_N4u8z3G2nLfp40CsX0kYIVXfzU6yf_n6T7ZCGXd6IlcY8yIv28h2GgBGItxMqDyc1WPbJb9qqqERCj7NGoNhqkOQ4-Gl2Uhg09KMfHpz-6THPd6E0maY1CsQ)

https://neerc.ifmo.ru/wiki/index.php?title=Карманная_Сортировка

1 шаг – устанавливаем отрезок через поиск max и min.

2 шаг – дробим отрезок на несколько отрезков «корзины» (buckets). Их размер считаем так:

bucketSize = (max – min) / blocks

3 шаг – Распределяем элементы по корзинам таким образом:

elementIndex = (arr[i] – min) / blocks

4 шаг:

1 вариант:

1. Каждую корзину разбиваем еще на несколько и повторяем шаги 2-4 до тех пор, пока в каждой корзине не останется по одному элементу;
2. Записываем все числа подряд

2 вариант

1. В каждой корзине применяем любою другую сортировку;
2. Записываем числа из корзин подряд.

Сложность по времени:

Лучший случай: O(n+k) в первом же делении в каждой корзине по одному числу

Средний случай: О(n+k)

Худший случай: O(n^2) если числа очень близки друг к другу по значению и почти все на первом же делении попали в одну корзину