Роберт Клаузекер и Флориан Шинтке представили исследовательскую работу о Radsort. В ней описан вариант LSD radix sort и его ключевые характеристики.

Radsort использует O(√n) дополнительной памяти. Алгоритм сохраняет стабильность сортировки, а его реализацию авторы называют простой.

Radsort легко распараллеливается. На массивах размером примерно более 2 МиБ он превосходит обычную LSD radix sort с размещением результата вне исходного массива.

Проверка утверждений:

  • Роберт Клаузекер и Флориан Шинтке представили исследовательскую работу о Radsort; она знакомит читателя с вариантом LSD radix sort и его ключевыми характеристиками. (подтверждено первоисточником: доказательство; «Title: Parallel $\mathcal O(\sqrt n)$ Overhead LSD Radix Sort Authors: Robert Clausecker , Florian Schintke View a PDF of the paper titled Parallel $\mathcal O(\sqrt n)$ Overhead LSD Radix Sort, by Robert Clausecker and Florian Schintke View PDF HTML (experimental) Abstract: We present Radsort, a variant of LSD radix sort, sorting data with $\mathcal O(\sqrt n)$ additional space.»)
  • Radsort сортирует данные, используя O(√n) дополнительной памяти. (подтверждено первоисточником: доказательство; «We present Radsort, a variant of LSD radix sort, sorting data with $\mathcal O(\sqrt n)$ additional space.»)
  • Radsort является стабильным алгоритмом сортировки. (подтверждено первоисточником: доказательство; «Radsort is stable, admits a simple implementation and is easy to parallelise.»)
  • Авторы характеризуют реализацию Radsort как простую. (подтверждено первоисточником: доказательство; «Radsort is stable, admits a simple implementation and is easy to parallelise.»)
  • Radsort легко распараллеливается. (подтверждено первоисточником: доказательство; «Radsort is stable, admits a simple implementation and is easy to parallelise.»)
  • На массивах размером примерно более 2 МиБ Radsort превосходит обычную LSD radix sort с размещением результата вне исходного массива. (подтверждено первоисточником: доказательство; «For arrays exceeding a size of around 2 MiB it outperforms a conventional out-of-place LSD radix sort.»)
  • Работа содержит 16 страниц и шесть иллюстраций. (подтверждено первоисточником: доказательство; «16 pages, 6 figures»)

Первоисточники:

оценка 68.2 · тип research · ревизия 1 · истории st-1frxhox