SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures

Summary: Introduces a SIMD- and cache-friendly vectorized multiway mergesort for sorting an array of structures, avoiding costly random rearrangements. Outperforms key-index SIMD and radix sort for large records, delivering up to 2.1x single-thread speedup on 512M 16-byte records and better multi-core scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11007
Venue: VLDB
Year: 2015
Pagerank: 6.0171025e-05
Overall Rank: 4,649 | 67.70%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Hiroshi Inoue
2. Kenjiro Taura

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,161	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	7.4648665e-05
4,086	The Case for a Learned Sorting Algorithm	2020	SIGMOD	6.4579358e-05
6,116	Database Processing-in-Memory: An Experimental Study	2020	VLDB	5.1995375e-05
7,095	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	4.8289712e-05
7,155	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD	4.810361e-05
8,368	Interleaved Multi-Vectorizing	2020	VLDB	4.5295768e-05
9,837	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	4.269939e-05
11,383	Origami: A High-Performance Mergesort Framework	2022	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
238	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00031596093
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026756534
350	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00026368305
403	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024176677
932	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015227954
944	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001512998
1,610	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011155922
1,758	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB	0.00010648185
3,449	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0803234e-05
3,660	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	6.8683099e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,840	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	4.1905499e-05
1,758	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB	0.00010648185
2,741	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.1977375e-05
959	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015034808
4,826	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8892345e-05
11,383	Origami: A High-Performance Mergesort Framework	2022	VLDB	4.1905499e-05
3,161	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	7.4648665e-05
1,610	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011155922
932	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015227954
944	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001512998