SashaMercury,

не ясно, какого сорта ответ ты хочешь услышать.

Сортировка за константу означает, что она не зависит от объема сортируемого набора данных.

Сама сортировка описывается в терминах перестановок элементов.
Пусть у тебя есть некий "массив массивов", то есть массив, каждый элемент которого сам является массивом.
Пусть такой массив содержит все перестановки для фиксированного мультимножества, из
которого составлен сортируемый набор.
Тогда в этом массиве будут две, для конкретного мультимножества заранее известные
известные позиции i_max и i_min, представляющие сортировку по возрастанию и сортировку
по убыванию для данного конкретного мультимножества.

Сортировка за константу сведётся к указанию заранее известных позиций i_max или i_min для конкретного мультимножества.

Все остальные позиции будут представлять
прочие варианты перестановки в мультимножестве, и в целях сортировки их можно не хранить, если заранее известно, что предназначенный для сортировки набор относится к тому, мультимножеству, для которого задаются идентификаторы сортировки (то есть не требуется процедура идентификации мультимножества).

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

Логически это значит, что все сортировки подсчетом, идентифицирующие мультимножество,
выполнены заранее и, дополнительно, процедура выполнения идентификации мультимножества не требует времени выполнения (константа на классификацию равна нулю). То есть добавление элемента сводится к указанию на соответствующий, заранее построенный массив перестановок (сведённый до двух элементов), представляющий
изменённое мультимножества после добавления нового элемента.

Что это означает?
В не квантовых терминах, вероятно, прежде всего то, что реализована память с
произвольным доступом неограниченного размера, доступ к любому элементу которой гарантируется за константу, и все алгоритмы поиска/сортировки заранее реализованы в ней в табличном виде.
То есть все состояния всех вычислительных процессов сортировки зафиксированы,
и динамика сводится к переходу по указателю на ту область памяти за константное время, которая хранит соответствующий сортированный набор.

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

Как-то так думаю.