Кажется там чувак закоммитил вместе с проектом исходник библиотеки, которую он использовал

угу

Ну там само доказательсто тоже внушительное, даже без вспомогательной библиотеки. Хотя не исключено что вероятно можно и проще было сделать

Там идеться речь про O(1/n). Хотя теоретически такое возможно обчно на практике не достижимо. А вот O(m/n) или O(1/n + c) что пости тоже самое что O(1)

Это к реплике "просто сверху ещё одну функцию добавили" и вопросу "нетрипичных" (незнакомых) моделей вычисления. 😊

Кстати есть сортировка быстре чем за O(n) для целых чисел
https://yourbasic.org/algorithms/fastest-sorting-algorithm

Это в догонку про нетипичные асимптотики

И как всегда такие алгоритмы опираются на частичное или полное распарралеливание

Быстрее, чем O(n), точно?

Ну на осязаемом прмежутке машинного слова в котором можно выразить макс колличество элементов скажем 2**32-1 то да

На мой взгляд, работа, где вообще не нужно разрабатывать/реализовывать алгоритмы -- это скучно.  Особенно, если это очередное проектирование "костюмов для собак" [1], пусть и с психологической компенсацией -- то есть с применением какого-то недоступного для большинства простолюдинов способа.

[1] Отсылка к известной фразе Р.Брэдбери.

Если взглянуть на общеупотребимое описание понятия "алгоритм", то станет сложно вообще найти такую работу, где не нужно разрабатывать/реализовывать хоть какие-то алгоритмы. 😉

я бы тогда лучше говорил про абстрактные типы данных)

Да, cache oblivious это интересно. Но на практике блочные подходы, все-таки, бывают эффективнее, поскольку они могут дать еще и параллелизм. По поводу параметров конкретной подсистемы памяти — на этот счет есть автоматические подходы на основе самонастройки. Это неплохо работает для выч. библиотек. Ваш пример, кстати говоря, показывает, насколько важно сегодня владеть фундаментальными алгоритмами для того, чтобы их использовать в новых контекстах, создавать гибридные варианты и проч. Если хочется увидеть применение менее популярных алгоритмических подходов — можно посмотреть в сторону массово-параллельных, распределенных систем.

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

Т.е. не "видя" какого-то элемента, ты можешь его место определить? Статья O(nloglogn) называется, по диагонали посмотрел ее, ничего удивительного не увидел, только кто-то с битами ковыряется

Статья написана на основе вот этой
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.6493&rep=rep1&type=pdf

И где там быстрее O(n)?

Там написано про линейное время тоже, асимптотики не настолько заоблачные в статье; ты про какую-то фантастику рассказываешь, я не могу понять -- это ты ошибся так, или всё-таки стоит прочитать статью?

Там же даже описано за счет чего это получается - комбинацией packed sorting (Paul and Simon) и range reduction (T. Hagerup and H. Shen. Improved nonconservative se-quential and parallel integer sorting  а так же S. Albers, T. Hagerup parallel integer sorting without concurrent writing)