FastSort: A Distributed Single-Input Single-Output External Sort

Summary: FastSort: distributed single-input single-output external sort on multi-processor systems with tournament replacement-selection and private disks. The paper analyzes the algorithm and reports performance, showing linear elapsed time and scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he52d389b42d8154b
Venue: SIGMOD
Year: 1990
Pagerank: 7.1098491e-05
Overall Rank: 3,672 | 75.32%
DOI: 10.1145/93597.98719

Incoming Non-self Citations Over Time

Authors

1. Betty Salzberg (Northeastern University)
2. Alex Tsukerman (Tandem Computers)
3. Jim Gray (Tandem Computers)
4. Michael Stewart (Tandem Computers)
5. Susan Uren (Tandem Computers)
6. Bonnie Vaughan (Tandem Computers)

BibTeX Citation

@inproceedings{salzberg_sigmod90,
        title = {{FastSort: A Distributed Single-Input Single-Output External Sort}},
        author = {Salzberg, Betty and Tsukerman, Alex and Gray, Jim and Stewart, Michael and Uren, Susan and Vaughan, Bonnie},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.98719},
        url = {https://dl.acm.org/doi/10.1145/93597.98719},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
304	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021604795
846	High-Performance Sorting on Networks of Workstations	1997	SIGMOD	0.00013522859
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010133792
4,469	Memory-Adaptive External Sorting	1993	VLDB	6.5854799e-05
6,690	Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships	1998	VLDB	5.7073875e-05
10,840	CrocSort: Resource-Efficient, Skew-Resilient Parallel External Merge Sort	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
54	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00040499302
1,314	A Low Communication Sort Algorithm for a Parallel Database Machine	1989	VLDB	0.00011058431

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,393	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD
2	661	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD
3	4,469	Memory-Adaptive External Sorting	1993	VLDB
4	722	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
5	2,161	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB
6	10,840	CrocSort: Resource-Efficient, Skew-Resilient Parallel External Merge Sort	2026	VLDB
7	8,617	Buffering and Read-Ahead Strategies for External Mergesort	1998	VLDB
8	1,314	A Low Communication Sort Algorithm for a Parallel Database Machine	1989	VLDB
9	7,854	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
10	4,692	Dynamic Memory Adjustment for External Mergesort	1997	VLDB