Сортировка аппроксимацией :: Proxmap Sort

Другие алгоритмы, использующие принципы приблизительного распределения и последующей вставки - флеш-сортировка и сортировка царя Соломона.
Визуализация похожа на сортировку «Американский флаг».
- Применяем аппроксимирующую функцию к каждому элементу, определяя, какому хиту соответствует очередной элемент.
- Таким образом для каждого хита можем подсчитать количество элементов, соответствующих данному хиту.
- Зная количества элементов для всех хитов, определяем локализации хитов (границы слева) в массиве.
- Зная локализации хитов, определяем локализацию каждого элемента.
- Определив локализацию элемента, пытаемся вставить его на своё место в массиве. Если место уже занято, то или сдвигаем соседей вправо (если элемент меньше их), чтобы освободить место для элемента. Или правее вставляем сам элемент (если он больше соседей).
Ссылки
Подсчёт с приблизительным распределением — чаще всего переизобретаемая сортировка