Title: Sorting n objects with a k-sorter

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.

Download Full Paper