В параллельных алгоритмах задача ранжирования списков включает определение позиции или ранга каждого элемента в связанном списке . То есть, первому элементу в списке следует присвоить номер 1, второму элементу в списке следует присвоить номер 2 и т. д. Хотя эту задачу легко решить эффективно на последовательном компьютере, обходя список по порядку, ее сложнее решить параллельно. Как писали Андерсон и Миллер (1990), эта задача считалась важной в сообществе параллельных алгоритмов как из-за ее многочисленных приложений, так и потому, что ее решение привело ко многим важным идеям, которые можно было бы применить в параллельных алгоритмах в более общем плане.
Проблема ранжирования списков была поставлена Уайли (1979), который решил ее с помощью параллельного алгоритма, использующего логарифмическое время и O( n log n ) общих шагов (то есть O( n ) процессоров). В ходе ряда последующих работ это в конечном итоге было улучшено до линейного числа шагов (O( n /log n ) процессоров) на самой ограничительной модели синхронных параллельных вычислений с общей памятью, исключительное чтение-исключительная запись PRAM (Vishkin 1984; Cole & Vishkin 1989;Anderson & Miller 1990). Это число шагов соответствует последовательному алгоритму.
Ранжирование списков можно эквивалентно рассматривать как выполнение операции префиксной суммы для данного списка, в которой все значения, которые нужно суммировать, равны единице. Задача ранжирования списков может использоваться для решения многих задач на деревьях с помощью техники тура Эйлера , в которой формируется связанный список, включающий две копии каждого ребра дерева, по одной в каждом направлении, помещает узлы этого списка в упорядоченный массив с использованием ранжирования списков, а затем выполняет вычисления префиксной суммы для упорядоченного массива (Tarjan & Vishkin 1985). Например, высота каждого узла в дереве может быть вычислена с помощью алгоритма этого типа, в котором префиксная сумма добавляет 1 для каждого нисходящего ребра и вычитает 1 для каждого восходящего ребра.