빠른 병렬 정렬 알고리즘

병렬 버킷 정렬 알고리즘이 제시되며, 이는 O(log n) 시간과 n 프로세서를 필요로 한다. 이 알고리즘은 프로세서와 시간의 곱보다 더 많은 공간을 요구하는 기법을 활용한다. 메모리 경합이 허용되지 않는 실용적인 모델이 사용된다. k가 임의의 정수일 때, n 1 + 1 / k 프로세서를 사용하여 n개의 숫자를 O(k log n) 시간에 정렬하는 절차도 제시된다. 이 절차의 계산 모델은 동일한 메모리 위치에서 동시에 데이터를 가져오는 것을 허용한다.