Sort Integers into a Linked List

摘要

We show that n integers in {0,1,..., m-1} can be sorted into a linked list in constant time using nlogm processors on the Priority CRCW PRAM model, and they can be sorted into a linked list in O(loglognVlogt) time using nt processors on the Priority CRCW PRAM model.