Authors: Richard Beigel and John Gill
Abstract: A k-sorter is a device that sorts k objects in unit time. We define the complexity of an algorithm that uses a k-sorter as the number of applications of the k-sorter. In this measure, the complexity of sorting n objects is between nlogn/klogk and 4nlogn/klogk, up to first order terms in n and k.