On sorting strings in external memory (extended abstract)

Abstract

In this paper we address for the first time the I/O complexity of the problem of sorting strings in external memory, which is a fundamental component of many large-scale text applications. In the standard unit-cost RAM comparison model, the complexity of ¤ sorting strings of total ¥ length ¦¨§©¤���������¤��¨¥� � is. By analogy, in the external memory (or I/O) model, where the internal memory has � size and the block transfer size � is, it would be natural to guess that the I/O complexity of sorting strings ¦¨§������������ � � �������� � is, but the known algorithms do not come even close to achieving this bound. Our results show, somewhat counterintuitively, that the I/O complexity of string sorting depends upon the length of the strings relative to the block size. We first consider a simple comparison I/O model, where one is not