Cubesort - Cubesort

Cubesort
Класс Алгоритм сортировки
Структура данных Массив
Пессимистический производительность O ( п войти п )
Сложность пространства в наихудшем случае Θ ( п )

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

Реализация cubesort, написанная на C, была опубликована в 2014 году.

Операция

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

Ссылки

внешние ссылки