Какие существуют библиотеки или алгоритмы генерации индексов для сортировки по-порядк
 

Пример:
В базе хранится массив

id| sortIndex
A | 1
B | 2
C | 3
D | 4

Допустим, мы поменяли в нем позицию элемента D. Стало:

id| sortIndex
A | 1
D | 2
B | 3
C | 4

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

Можно сделать по-другому, например, так:

id| sortIndex
A | 1
D | 1,5
B | 2
C | 3

Тут мы вычисляем новый индекс как среднее арифметическое от индекса соседей. Соответственно в базе меняется только один элемент.

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

В общем, кто какие решения знает?

Почему все, и почему элементы, может быть порядок их сортировки, а не они сами?

тоже так думаю) похоже на обычный серверный swap

не будут

если сортировка не по sortIndex работать будет криво

К сожалению в базе нет swap, хотя можно и процедуру написать ) Нужен обычный UPDATE колонке sortIndex - для тех записей, которые больше и равные новой позиции, +1, которые меньше, -1.

Никаких эффективных алгоритмов :) в вашем случае на сервер надо передать изменившиеся данные, а значит
D | 2
B | 3
C | 4
все остальное обрабатываем на сервере

Передавать тупо все данные проще всего, но слишком ресурсоемко, а поэтому применимо лишь для небольших списков.

Пробовал так же передавать массив айдишников в новом порядке (пример: http://tamtakoe.ru/photoalbum). Неплохо, но опять же для больших списков избыточно. Так же предыдущие способы не совместимы с пагинацией.

Сейчас задача сделать универсальный механизм сортировки для админки. А там могут быть списки из 20 элементов и из 2000 и больше. Естественно, везде пагинация. С другой стороны сортировка — достаточно редкая операция.

Передавать куда? Впечатление, что у вас вымышленная проблема. В любом случае на клиента передается все и не важно постранично или нет, и если в этом писке нужно определить новый порядок сортировки, то не передав на сервер значения, порядок нельзя изменить.

Не охота все перебирать, так запоминайте на сервере текущий порядок, а по приему формы обновляйте те записи, порядок которых изменился.

Сортировка, это почти постоянная операция при выборе из базы, а вот задание порядка сортировки и ее изменение, так тут бабушка надвое сказала, бывает, что и часто.

Логика есть. Порядок скорее всего будет меняться в пределах 1-2 страниц. А это не так уж много элементов. Тогда надо сохранить, например, 20 элементов с измененными позициями. Как это сделать по RESTу? Послать 20 запросов

POST /items/<id>

?

Пользовательская сортировка определяется для чего, для таблицы базы данных? Если да, то причем тут непосредственно способ передачи данных?

Да, для БД. Тут важно всё и способ передачи данных в том числе. Если в одном месте станет красиво, а в другом коряво, то смысла в решении нет.