A Study of Sort Algorithms for Multiprocessor Database Machines

Summary: Analysis of internal and external sorting on general multiprocessors, replacing comparison-exchange with B-way merges. Introduces modified block bitonic sort, combining pipelining and parallel internal sorting; fastest broadly and best exploiting extra buffer memory. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h832eb624b7b87eec
Venue: VLDB
Year: 1986
Pagerank: 5.4401441e-05
Overall Rank: 7,854 | 47.20%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jai Menon (IBM)

BibTeX Citation

@article{menon_vldb86,
        title = {{A Study of Sort Algorithms for Multiprocessor Database Machines}},
        author = {Menon, Jai},
        journal = {PVLDB},
        series = {{VLDB} '86},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010133792
6,690	Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships	1998	VLDB	5.7073875e-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
82	Hashing Methods and Relational Algebra Operations	1984	VLDB	0.00036053776
2,206	Query Execution in DIRECT	1979	SIGMOD	8.8527448e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,161	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB
2	722	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
3	1,539	Sorting And Indexing With Partitioned B-Trees	2003	CIDR
4	423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB
5	6,829	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB
6	3,672	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD
7	4,469	Memory-Adaptive External Sorting	1993	VLDB
8	1,116	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
9	4,692	Dynamic Memory Adjustment for External Mergesort	1997	VLDB
10	1,314	A Low Communication Sort Algorithm for a Parallel Database Machine	1989	VLDB