Здравствуйте, Sinclair, Вы писали:

S>Исходный — нет, но за nlogn его можно сделать возрастающим.
шо за пургу ты несёшь ? как ты одномерный массив состоящий из пар (10, 2), (1, 5) сделаешь одномерно возрастающим ? (так чтобы пары сохранились в последовательности)

S>Произвольно, заранее неизвестно.
натуральные или целые ? обычные int 4 байта ?

S>В пределах миллисекунды
взаимоисключающие требования на чём миллисекунда то, на CPU (однопоток/многопоток?) или GPGPU ? (ну и как бэ разница есть, 3000G это или 7950X, 3050 или 4090)

ну и приблизительно сколько чисел — тысячи / миллионы или миллиарды ? (в последнем случае на миллисекунду думаю что рассчитывать маловероятно)

S>Ну, что было — то представил. Покажите пример вашего ТЗ для алгоритма, чтобы у меня был образец для подражания.

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