Microsystems Minimal Storage Sorting and Searching Techniques for RAM Applications: a Tutorial

A large number of sorting and searching techniques, covering a variety of applications, are dealt with in computer science literature. The classical problem associated with these methods has been determining which set of algorithms is most appropriate for a given application. With the recent advances in LSI technology and the assured proliferation of microprocessors and RAM memory, yet another application has evolved. Memory address widths associated with microprocessor systems are limited, in many cases, to a maximum of 16 bits, severely restricting maximum memory size. Minimal storage implementation techniques, characterized by the optimal use of the data space associated with an algorithm, therefore, are most appropriate for these restricted address space environments common to microprocessor systems.