Skip to main content

NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

The New Golden Age of Algorithms and Data Structures

Published

Author(s)

Paul E. Black

Abstract

Before 1976 Communications of the ACM printed (and numbered!) new algorithms every issue. Quicksort was invented in 1960, Boyer-Moore string search in 1977, and combsort in 1980. I haven't seen a new, general sorting algorithm in over a decade. The latest "general" data structure is the skip list, which was invented in 1990. Have all the basic, general algorithms and data structures been invented? We don't think so. With isochronous computing, heterogeneous multiprocessors, energy aware computing, wear-leveling (flash), cache and other anisotropic memory, distributed computing, streaming environments, functional languages, etc. there is a great need for research into new fundamental algorithms and data structures. As examples, we take the bulk of the time to present four which are novel and useful: reservoir sampling, majority on a stream, B-heap, and compacting and array in O(log n) time.

Keywords

algorithms, data structures

Citation

Black, P. (2012), The New Golden Age of Algorithms and Data Structures (Accessed October 2, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created October 29, 2012, Updated February 19, 2017
Was this page helpful?