Я работал как с алгоритмом параллельной быстрой сортировки, так и с алгоритмом PSRS, который по существу объединяет быструю сортировку параллельно со слиянием.
С помощью алгоритма параллельной быстрой сортировки я продемонстрировал почти линейное ускорение с использованием до 4 ядер (двойнойядро с гиперпоточностью), что ожидается с учетом ограничений алгоритма.Чистая параллельная быстрая сортировка основывается на ресурсе общего стека, что приведет к конфликту между потоками, что приведет к снижению производительностиПреимущество этого алгоритма состоит в том, что он сортирует «на месте», что уменьшает объем необходимой памяти.Возможно, вы захотите учесть это при сортировке более 100 млн элементов, как вы заявили.
Я вижу, что вы собираетесь сортировать систему с 8-32 ядрами.Алгоритм PSRS позволяет избежать конфликтов на общем ресурсе, что позволяет ускорить процесс при большем количестве процессов.Я продемонстрировал алгоритм с 4 ядрами, как указано выше, но экспериментальные результаты других показывают почти линейное ускорение с гораздо большим числом ядер, 32 и более.Недостатком алгоритма PSRS является то, что он не на месте и потребует значительно больше памяти.
Если вы заинтересованы, вы можете использовать или просмотреть мой Java-код для каждого из этих алгоритмов.Вы можете найти его на github: https://github.com/broadbear/sort. Код предназначен для быстрой замены Java Collections.sort ().Если вы ищете возможность выполнять параллельную сортировку в JVM, как вы заявили выше, код в моем репо может вам помочь.API полностью обобщен для элементов, реализующих Comparable или реализующих ваш собственный Comparator.
Могу ли я спросить, для чего вы хотите отсортировать такое количество элементов?Мне интересно узнать о потенциальных приложениях для моего пакета сортировки.